svg_af's blog

By svg_af, history, 8 years ago, In English

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";
        }
    }
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it