Submission #474232

#	Time	Username	Problem	Language	Result	Execution time	Memory
474232		teee	Treasure Hunt (CEOI11_tre)	C++17	0 / 100	4056 ms	187212 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
struct node;
map<int,node*> mp;
struct node{
    node *l,*r,*p;
    int Mcnt,Scnt,key;
    int lef;
    bool rev;
    node(int a,int b){
        l=r=p= nullptr;
        Mcnt=Scnt=b;
        key=a;
        rev=false;
        lef=key;
    }
};
bool isRoot(node * x) {
    return (!x->p || (x->p->l != x && x->p->r != x));
}
void lazy_up(node* x){
    if(!x)return;
    if(x->rev){
        if(x->l)x->l->rev^=1,swap(x->l->l,x->l->r);
        if(x->r)x->r->rev^=1,swap(x->r->l,x->r->r);
        x->rev=false;
    }
}
void update(node* x){
    lazy_up(x);
    lazy_up(x->l);
    lazy_up(x->r);
    x->Scnt=x->Mcnt;
    x->lef=x->key;
    if(x->l){
        x->Scnt+=x->l->Scnt;
        x->lef=x->l->lef;
    }
    if(x->r)x->Scnt+=x->r->Scnt;
}
void rotate(node* x){
    node* p=x->p;
    lazy_up(p);lazy_up(x);
    update(x);update(p);
    if(x==p->l){
        p->l=x->r;
        if(p->l)p->l->p=p;
        x->r=p;
    }else{
        p->r=x->l;
        if(p->r)p->r->p=p;
        x->l=p;
    }
    x->p=p->p;
    p->p=x;
    lazy_up(p);lazy_up(x);
    update(x);update(p);
    if(x->p){
        if(p==x->p->l)x->p->l=x;
        else if(p==x->p->r)x->p->r=x;
    }
    lazy_up(p);lazy_up(x);
    update(x);update(p);
}

void splay(node* x){///thinking
    while(!isRoot(x)){
        node* p=x->p;
        if (!isRoot(p)) lazy_up(p->p);
        lazy_up(p);
        lazy_up(x);
        update(x);update(p);
        if(!isRoot(p)){
            if((x==p->l)^(p==p->p->l))rotate(x);
            else rotate(p);
        }
        rotate(x);
    }
    lazy_up(x);update(x);
}
node* access(node* x){//////////thinking
    lazy_up(x);update(x);
    splay(x);
    lazy_up(x);update(x);
    x->r= nullptr;
    node* res=x;
    while(x->p){
        node* p=x->p;
        res=p;
        splay(p);
        p->r=x;
        splay(x);
    }
    lazy_up(x);update(x);
    return res;
}
void makeRoot(node * x) {
    access(x);
    swap(x->l,x->r);
    x->rev = true;
    lazy_up(x);
}
int now;
void init(){
    mp[1]=new node(1,1);
    now=2;
}
node* split(node* p,int a){/////////누구한테 자식을 뭘 줄지 오더는 어캐 할지
    if(p->Mcnt==1)return p;
    if(p->key==a){
        node* pp=new node(a,1);
        mp[a]=pp;
        p->key++;p->Mcnt--;
        mp[a+1]=p;
        p->p=pp;pp->r=p;
        p->l=pp->l;
        if(pp->l)pp->l->p=p;
        pp->l=nullptr;
        update(pp);
        update(p);p=pp;
    }else{/////////////////
        int k=a-p->key;///l
        int nk=p->Mcnt-k-1;////r
        if(nk){
            node* pp=new node(a,1);
            mp[a]=pp;
            node*lp=new node(p->key,k);
            mp[p->key]=lp;
            p->Mcnt=nk;p->key=a+1;
            mp[a+1]=p;
            pp->r=p;p->p=pp;
            lp->r=pp;pp->p=lp;
            lp->l=p->l;
            if(p->l)p->l->p=lp;
            p->l=nullptr;
            update(p);
            update(pp);
            update(lp);p=pp;
        }else{
            node*lp=new node(p->key,k);
            mp[p->key]=lp;
            p->key=a;p->Mcnt=1;
            mp[a]=p;
            lp->r=p;
            p->p=lp;
            lp->l=p->l;
            if(p->l)p->l->p=lp;
            p->l=nullptr;
            update(p);
            update(lp);
        }
    }
    return p;
}
void path(int a, int s){
    node* p=prev(mp.upper_bound(a))->second;
    access(p);
    p=split(p,a);
    node* q=new node(now,s);
    mp[now]=q;
    q->p=p;p->r=q;
    access(q);
    now+=s;
}

int dig2(int a, int b){
    node* p=prev(mp.upper_bound(a))->second;
    node* pp=prev(mp.upper_bound(b))->second;
    access(p);p=split(p,a);
    access(pp);pp=split(pp,b);
    makeRoot(p);
    access(pp);
    splay(p);
    int cnt=(p->Scnt+1)/2;///몇칸 갈거임?
    while(1){
        update(p);
        while(p->l&&p->l->Scnt >= cnt){
            p=p->l;update(p);
        }
        if(p->l)cnt-=p->l->Scnt;
        if(p->Mcnt >= cnt){
            if(cnt==1)return p->key;
            if(p->lef < p->key){
                return p->key+cnt-1;
            }return p->key+p->Mcnt-1-cnt+1;
        }cnt-=p->Mcnt;
        p=p->r;
    }
}int dig(int a, int b){
    int ans=dig2(a,b);
    node*p=mp[1];
    access(p);
    makeRoot(p);
    cout<<ans<<'\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10