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) whichisshould be acceptable?↵
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
