IT GOT ACCEPTED
BUT CHANGING THE LAST ELSE PART IS GIVING ME TLE
WHY?
else{
//count no of elements less than x
ll an=lower_bound(a.begin(),a.end(),v[i].second)-a.begin();
if(an<0)printf(“0\n”);
else
printf("%d\n",query(1,1,a.size(),1,an));
}
ACCEPTED CODE:
#include
#include
#include
#include<unordered_map>
#define ll int
using namespace std;
ll tree[800001];
vector<pair<char,ll> > v;
vectora;
unordered_map<ll,ll> m;
ll search(ll ct,ll s,ll e,ll v){
if(s==e){
return s;
}
ll mid=(s+e)/2;
if(tree[2ct]>=v)
return search(2ct,s,mid,v);
else
return search(2ct+1,mid+1,e,v-tree[2ct]);
}
ll query(ll ct,ll s,ll e,ll sv,ll ev){
if(s>=sv&&e<=ev){
return tree[ct];
}
ll mid=(s+e)/2;
if(ev<=mid)
return query(2ct,s,mid,sv,ev);
else if(sv>mid)
return query(2ct+1,mid+1,e,sv,ev);
else
return query(2ct,s,mid,sv,ev)+query(2ct+1,mid+1,e,sv,ev);
}
void update(ll ct,ll s,ll e,ll v,ll k){
if(s==e&&s==v){
tree[ct]+=k;
return;
}
ll mid=(s+e)/2;
if(v<=mid)
update(2ct,s,mid,v,k);
else
update(2ct+1,mid+1,e,v,k);
tree[ct]=tree[2ct]+tree[2ct+1];
}
int main(){
ll n;
scanf("%d",&n);
a.clear();
m.clear();
v.clear();
for(ll i=0;i<n;i++){
char c;ll d;
cin>>c;
scanf("%d",&d);
v.push_back(make_pair(c,d));
m[d]=1;
}
for(auto i:m){
a.push_back(i.first);
}
sort(a.begin(),a.end());
for(ll i=0;i<a.size();i++){m[a[i]]=i+1;}
for(ll i=0;i<n;i++){
if(v[i].first==‘I’){
if(query(1,1,a.size(),m[v[i].second],m[v[i].second])==0) {
update(1,1,a.size(),m[v[i].second],1);}
}
else if(v[i].first==‘D’){
if(query(1,1,a.size(),m[v[i].second],m[v[i].second]))
update(1,1,a.size(),m[v[i].second],-1);
}
else if(v[i].first==‘K’){
ll ans=0;
//kth smallest element
if(tree[1]>=v[i].second){
ans=search(1,1,a.size(),v[i].second);
printf("%d\n",a[ans-1]);}
else
printf(“invalid\n”);
}
else{
//count no of elements less than x
ll an=lower_bound(a.begin(),a.end(),v[i].second)-a.begin();
an–;
if(an<0)printf(“0\n”);
else
printf("%d\n",query(1,1,a.size(),1,m[a[an]]));
}
}
}