# Solve Time Limit Exceeded for list<int> in c++

The input begins with an integer $q, 1 \leq q \leq 10^5$, the number of queries. The next $q$ lines each gives a query. A query is $\text{"a x"}, 1 \leq x \leq 10^9$

Print the result of each query on a single line. For each a query, print the last integer in the queue that is smaller than $x$. If there is no such integer, print $-1$.

Why my code could cause time limit exceeded?

#include <iostream>
#include <list>
using namespace std;

list<int> mylist;

int searchSmall(){
list<int>::const_iterator i;
for (i = mylist.begin(); i != mylist.end(); ++i){
if(*i < mylist.front()){
return *i;
}
}
return -1;
}

int main (){
int n;
ios_base::sync_with_stdio(false);
cin >> n;
while(n--){
char e;
cin >> e;
if(e == 'a'){
int q;
cin >> q;
mylist.push_front(q);
cout << searchSmall() << endl;
}
}
return 0;
}

• Please complete the problem statement, make it a block quote, and provide a hyperlink to its source. Your question is at the verge of being off topic for not asking for a review, but the reason for TLE. – greybeard Feb 14 '18 at 9:24

Don't use using namespace std;

You don't say what platform you're on or what time limit is being exceeded, but for performance, replace

#include <list>
list<int> mylist;


with

#include <vector>
std::vector<int> mylist;


and

mylist.push_front(q);


with

mylist.push_back(q);


and re-measure. This will be much faster

• and, as Roland says, use '\n' instead of std::endl – cdmh Feb 14 '18 at 15:10
This is a classical range query problem. You get a TLE most likely because you're using a linear time data structure. Based on the input size (worst case) you'll have to spend C*10^5 * 10^10 cycles processing which would probably lead to a TLE in most OJs. Consider using a priority_queue or a binary tree to order your data for $\log(n)$ access. Namely, you should try changing your list to a priority_queue and then perform insertion and lookup using the priority queue/tree. This gives you a worst-case time complexity of $O(n \log n)$.
Do not use std::endl. Use a simple "\n" instead. Investigate the reasons yourself.