-4
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Feb 14, 2018 at 9:24

3 Answers 3

3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ and, as Roland says, use '\n' instead of std::endl \$\endgroup\$
    – cdmh
    Feb 14, 2018 at 15:10
  • \$\begingroup\$ Martin York - please don’t edit my answer to add your advice in my name. Add your own comments and attribute them appropriately \$\endgroup\$
    – cdmh
    Feb 15, 2018 at 7:54
3
\$\begingroup\$

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)\$.

\$\endgroup\$
1
\$\begingroup\$

Do not use std::endl. Use a simple "\n" instead. Investigate the reasons yourself.

If the above does not help, measure the performance on your local computer and provide more details than a simple "it is too slow".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.