oj.uz

Submission #103080

# Submission time Handle Problem Language Result Execution time Memory
103080 2019-03-29T02:27:27 Z LittleFlowers__ Examination (JOI19_examination) C++14
2 / 100
 3000 ms 48796 KB 
#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);
    }
    int ans(id x,int i){
        if(x==F) return 0;
        if(x->V>=i) return ans(x->L,i) + x->R->S+1;
        return ans(x->R,i);
    }
    void add(int x){
        id y=init(x);
        dfs(G,y);
        splay(y);
        G=y;

    }
    int get(int x){
        return ans(G,x);
    }
}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

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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 11 ms 1664 KB Output is correct
8 Correct 13 ms 1760 KB Output is correct
9 Correct 11 ms 1792 KB Output is correct
10 Correct 8 ms 1792 KB Output is correct
11 Correct 10 ms 1024 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 14 ms 1792 KB Output is correct
14 Correct 14 ms 1792 KB Output is correct
15 Correct 15 ms 1764 KB Output is correct
16 Correct 10 ms 768 KB Output is correct
17 Correct 25 ms 1664 KB Output is correct
18 Correct 5 ms 768 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 48796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 48796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 11 ms 1664 KB Output is correct
8 Correct 13 ms 1760 KB Output is correct
9 Correct 11 ms 1792 KB Output is correct
10 Correct 8 ms 1792 KB Output is correct
11 Correct 10 ms 1024 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 14 ms 1792 KB Output is correct
14 Correct 14 ms 1792 KB Output is correct
15 Correct 15 ms 1764 KB Output is correct
16 Correct 10 ms 768 KB Output is correct
17 Correct 25 ms 1664 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Execution timed out 3018 ms 48796 KB Time limit exceeded
20 Halted 0 ms 0 KB -