Submission #103077

#	Time	Username	Problem	Language	Result	Execution time	Memory
103077		LittleFlowers__	Examination (JOI19_examination)	C++14	0 / 100	748 ms	49940 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define task "EXAMiNATION"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int N=100010;

int n,q;
struct tp{int x,y,z,i;}a[N],t[N];

int ans[N];
vector<int> val;


struct CTDL{
    struct oo;
    typedef oo* id;

    struct oo{
        id L,R,P;
        int S,V;
    };
    id F,G;
    void build(){
        F=new oo;
        F->S=F->V=0;
        F->P=F->L=F->R=F;
        G=F;
    }
    id init(int x){
        id y=new oo;
        y->P=y->L=y->R=F;
        y->S=1; y->V=x;
        return y;
    }
    void down(id x){x->S=x->L->S+x->R->S+1;}
    void lef(id p,id u){p->L=u,u->P=p;}
    void rig(id p,id u){p->R=u,u->P=p;}
    void up(id x){
        id y=x->P, z=y->P;
        if(y->L==x) lef(y,x->R),rig(x,y);
        else        rig(y,x->L),lef(x,y);
        if(z->L==y) lef(z,x);
        else        rig(z,x);
        down(x),down(y);
    }
    void splay(id x){
        for(;;){
            id y=x->P,z=y->P;
            if(y==F) return;
            if(z!=F) if((z->L==y)==(y->L==x)) up(y);
                     else up(x);
            up(x);
        }
    }
    id pos(id x,int i){
        if(x==F) return x;
        if(x->L->V>=i) return pos(x->L,i);
        if(x->V<i) return pos(x->R,i);
        return x;
    }
    void dfs(id x,id y){
        if(x==F) return;
        if(x->V<y->V){
            if(x->R==F) rig(x,y);
            else dfs(x->R,y);
        }
        else{
            if(x->L==F) lef(x,y);
            else dfs(x->L,y);
        }
        down(x);
    }
    void add(int x){
        id y=init(x);
        dfs(G,y);
        splay(y);
        G=y;

    }
    int get(int x){
        id tmp=pos(G,x);
        if(tmp==F) return 0;
        splay(tmp);
        int ret=tmp->R->S + 1;
        splay(G);
        return ret;
    }
}T[N];


void upd(int i,int x){
    for(;i;i-=i&-i) T[i].add(x);
}
int que(int i,int x){
    i=lower_bound(all(val),i)-val.begin()+1;
    int ret=0;
    for(;i<=val.size();i+=i&-i) ret+=T[i].get(x);
    return ret;
}

signed main(){
    //freopen("EXAMiNATION.inp","r",stdin);
    //freopen("EXAMiNATION.out","w",stdout);
    n=in,q=in;
    forinc(i,1,n){
        int x=in,y=in; a[i]={x,y,x+y}; val.pb(x);
    }
    forinc(i,1,q) t[i]={in,in,in,i};

    sort(all(val)); val.erase(unique(all(val)),val.end());
    forinc(i,1,n) a[i].x=lower_bound(all(val),a[i].x)-val.begin()+1;

    sort(a+1,a+n+1,[](tp i, tp j){return i.z>j.z;});
    sort(t+1,t+q+1,[](tp i, tp j){return i.z>j.z;});
    forinc(i,1,val.size()) T[i].build();
    int j=1;
    forinc(i,1,q){
        while(j<=n && a[j].z>=t[i].z){
            upd(a[j].x,a[j].y); j++;
        }
        ans[t[i].i]=que(t[i].x,t[i].y);
    }
    forinc(i,1,q) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In member function 'void CTDL::splay(CTDL::id)':
examination.cpp:67:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(z!=F) if((z->L==y)==(y->L==x)) up(y);
               ^
examination.cpp: In function 'long long int que(long long int, long long int)':
examination.cpp:114:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i) ret+=T[i].get(x);
          ~^~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57