bitthal04's blog

Reason for TLE?
By bitthal04, history, 8 months ago, In English

https://mirror.codeforces.com/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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bitthal04 (previous revision, new revision, compare).

→ Reply
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
ll n;
cin>>n;

ll arr[n];

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::vector or arr[500000] (in the second case arr should be global I think...? I'm not very sure)

→ Reply
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply