Time limit exceeded

help
1

what is the time complexity of this code ? help me.

#include<bits/stdc++.h>
using namespace std;

int32_t  main(){
    int n,m;  scanf("%d",&n);
    vector<int> vs(n);
    for(auto &t : vs)scanf("%d",&t);
    scanf("%d",&m);
    vector<int> va(m);
    for(auto &t : va)scanf("%d",&t);
		
    set<int,greater<int>> st;
    for(int i=0;i<n;i++){
>            st.emplace(vs[i]);
    }
    for(int i=0;i<m;i++){
           st.emplace(va[i]);
           auto it=st.find(va[i]);
           int pos=distance(st.begin(),it)+1;
	         printf("%d\n",pos);
    }
    return 0;
}	
          printf("%ld\n",pos);
    }
    return 0;
}
3

It doesn’t actually compile, so technically \mathcal{O}(1) :stuck_out_tongue:

But seriously, approx :

\mathcal{O}(n + m + n log n + m log (n + m) + m (n + m))

4 Likes
4

m2 for which term

5

m(m+n) for which term

6

Set iterator are not random access iterators. So the distance function is O(\text{distance between the iterators}).

3 Likes
7 
for(int i=0;i<m;i++)
{
           // ...
           int pos=distance(st.begin(),it)+1; // O(n + m)
           // ...
}
2 Likes
8

O(m2) for the find in the loop. not it is set find it takes log(n)

9

I think that is for distance. I didn’t knew that there was distance available for set :pensive: Glad that I today learned new thing

10

Why it take O(n+m) ?

11

Max distance can be n+m and it is m times

1 Like
12

okk, thanks for discussion.

13

As @aneee004 said, distance takes time proportional to the distance between the iterators, which is proportional to the number of elements in the set, which is \mathcal{O}(n + m).

4 Likes
14

It manually moves the iterator with it++ until it gets to the second provided iterator. If you haven’t noticed, you cannot write it2 = it + 3 or s.begin() < s.end() with set iterators.

These are possible with vector iterators, because they are random access iterators.

4 Likes
15

oh !,it’s really helpful .thanks for help.