Hello there
I'm trying to slove this problem using segment tree
i'm trying to process the queries offline and doing data compression on the given numbers
but i keep getting WA and I've been trying to look for the reason for a couple of days with no use
if someone could find where i am mistaken that would be great :D
here is my code
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin);
#define writeFile freopen("output","w",stdout);
#define fastIO ios::sync_with_stdio(0);
typedef pair<int,int> ii;
typedef long long ll;
const int N = 200005;
int n;
map<int,int> chash;
int rev[N];
vector<pair<char,int> > query;
vector<int> inserts;
int tree[2<<19];
int cnt=0;
void insert(int node,int l,int r,int idx){
if (l==r) {
if (!tree[node]) cnt++;
tree[node] = 1;
return;
}
int mid = (l+r)>>1;
if (idx>mid) insert(node<<1|1,mid+1,r,idx);
else insert(node<<1,l,mid,idx);
tree[node] = tree[node<<1]+tree[node<<1|1];
}
void deleter(int node,int l,int r,int idx){
if (l==r){
if (tree[node]) cnt--;
tree[node] = 0;
return;
}
int mid = (l+r)>>1;
if (idx<=mid)
deleter(node<<1,l,mid,idx);
else
deleter(node<<1|1,mid+1,r,idx);
tree[node] = tree[node<<1]+tree[node<<1|1];
}
int getk(int node,int l,int r,int k){
if (l==r) return rev[l];
int mid = (l+r)>>1;
if (k<=tree[node<<1])
return getk(node<<1,l,mid,k);
return getk(node<<1|1,mid+1,r,k-tree[node<<1]);
}
int queryk(int node,int l,int r,int x){
if (l==r) return 0;
int mid=(l+r)>>1;
if (x<=mid) return queryk(node<<1,l,mid,x);
return tree[node<<1]+queryk(node<<1|1,mid+1,r,x);
}
int main(){
#ifndef ONLINE_JUDGE
readFile;
#endif
fastIO;
cin>>n;
for(int i=0;i<n;i++){
char c; int num; cin>>c>>num;
query.push_back(make_pair(c,num));
inserts.push_back(num);
}
sort(inserts.begin(),inserts.end());
int pointer=1;
chash[inserts[0]] = pointer;
rev[pointer++] = inserts[0];
for(int i=1;i<inserts.size();i++){
if (inserts[i]!=inserts[i-1]){
chash[inserts[i]] = pointer;
rev[pointer++] = inserts[i];
}
}
memset(tree,0,sizeof(tree));
for(int i=0;i<query.size();i++){
if (query[i].first=='I') {
insert(1,1,n,chash[query[i].second]);
continue;
}
if (query[i].first=='D') {
deleter(1,1,n,chash[query[i].second]);
continue;
}
if (query[i].first=='K') {
if (query[i].second>cnt) cout<<"INVALID\n";
else cout<<getk(1,1,n,min(N,query[i].second))<<"\n";
continue;
}
if (query[i].first=='C') {
cout<<queryk(1,1,n,chash[query[i].second])<<"\n";
}
}
}
Nevermind i found the error and got ac :D