https://codeforces.me/contest/2031/problem/D Problem link.
ll n;
cin>>n;
ll arr[n];
vector<ll> gret(n);
map <ll,ll,greater<ll>> mp;
for(int i=0;i<n;i++){
cin>>arr[i];
gret[i]=arr[i];
if(i>0)
gret[i]=max(gret[i],gret[i-1]);
if(mp.find(arr[i])==mp.end())
mp[arr[i]]=i;
}
auto it=mp.begin();
ll cnt=0;
ll mi=it->first;
ll ans[n];
int i=it->second,la=n;
while(cnt<n){
int q=i;
for(;i<la;i++){
ans[i]=it->first;
mi=min(mi,arr[i]);
cnt++;
}
la=q;
if(cnt==n)
break;
int k=upper_bound(gret.begin(),gret.end(),mi)-gret.begin();
if(mi==it->first || gret[k]==it->first){
it=mp.find(gret[la-1]);
i=it->second;
}
else{
i=k;
}
}
for(int j=0;j<n;j++)
cout<<ans[j]<<" ";
cout<<endl;This is the code. I am not able to get why I am getting TLE when the code complexity should be O(nlogn) which should be acceptable?
Auto comment: topic has been updated by bitthal04 (previous revision, new revision, compare).
This is simply wrong and doesn't even compile on some specific compilers. C-arrays should have a size that could be determined by the compiler (at compile time). However, there is no way for the compiler to determine how much memory it should use for
arr, resulting in undefined behavior.Just use
std::vectororarr[500000](in the second case arr should be global I think...? I'm not very sure)He only give a code, without int main() and other stuff.
OK, it did not get AC (submission is probably https://codeforces.me/contest/2031/submission/340028740 btw), but still, one day he will get a weird verdict because of this (i am talking from my personal experience)
Hmm, i think because of:
while (cnt < n) + it = mp.find(gret[la - 1])because only find() works in O(n) in vector, but in map, where you can get elements in O(log(n)) you will get a (n log(n)) only with that.mp.find() should take log(n) but it will happen at max n times making it nlog(n) for the whole while loop where n is 5e5. So it should work for a n like that I guess. Correct me if I am missing some calculation.