Submission #433283

#	Time	Username	Problem	Language	Result	Execution time	Memory
433283		Abelyan	Handcrafted Gift (IOI20_gift)	C++17	45 / 100	1588 ms	32712 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
using namespace std;


#define FOR(i,n) for (int i=0;i<(n);++i)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,a,b) for (int i=(a);i>=(b);--i)
#define FORD(i,n) for (int i=(n)-1;i>=0;--i)
#define trav(to,v) for (auto to : v)
#define fr first
#define sc second
#define pir pair<int,int> 
#define mpr make_pair
#define all(v) v.begin(),v.end()
#define ad push_back

mt19937 rng(5165);
typedef long long ll;
struct item{
    int val,mn,lz,prior,sz;
    item *l, *r;
    item(){
        val=mn=lz=0;
        sz=1;
        l=r=NULL;
        prior=rng();
    }
};

typedef struct item * pitem;

const int N=5e5+6;
pitem getitem(){
    static item nodes[N];
    static int counter=0;
    return &nodes[counter++];
}


int size(pitem t){
    if (t)return t->sz;
    return 0;
}
int mn(pitem t){
    if (t)return t->mn;
    return 1;
}

void upd(pitem t){
    if (!t)return;
    t->sz=size(t->l)+size(t->r)+1;
    t->mn=min(min(mn(t->l),mn(t->r)),t->val);
}

void make(pitem t){
    if (t){
        t->val=1;
        t->mn=1;
        t->lz=1;
    }

}

void push(pitem t){
    if (t && t->lz){
        make(t->l);
        make(t->r);
        t->lz=0;
    }
}

void merge(pitem &t,pitem l,pitem r){
    if (!l){
        t=r;
        return;
    }
    if (!r){
        t=l;
        return;
    }
    if (l->prior>r->prior){
        push(l);
        merge(l->r,l->r,r);
        t=l;
    }
    else{
        push(r);
        merge(r->l,l,r->l);
        t=r;
    }
    upd(t);
}

void split(pitem t,pitem &l,pitem &r,int key,int cur=0){
    if (!t){
        l=r=NULL;
        return;
    }
    //cout<<size(t->l)<<" "<<size(t)<<" "<<cur<<" "<<key<<endl;
    push(t);
    if (key<=cur+size(t->l)){
        split(t->l,l,t->l,key,cur);
        r=t;
    }
    else{
        split(t->r,t->r,r,key,cur+1+size(t->l));
        l=t;
    }
    upd(t);
}

void pb(pitem &t){
    pitem tv=getitem();
    merge(t,t,tv);
}

void print(pitem t){
    if (!t)return;
    push(t);
    print(t->l);
    cout<<t->val<<" ";
    print(t->r);
}

void cutmk(pitem &t,int l,int r){
    pitem a1,a2,a3;
    //cout<<l<<" "<<r<<endl;
    //print(t);
    //cout<<endl;
    split(t,a2,a3,r+1);
    //print(a2);
    //cout<<endl;
    split(a2,a1,a2,l);
    //print(a1);
    //cout<<endl;
    //print(a2);
    //cout<<endl;
    //print(a3);
    //cout<<endl;
    make(a2);
    //print(a2);
    //cout<<endl;
    merge(t,a1,a2);
    //print(a3);
    //cout<<endl;
    merge(t,t,a3);
    //print(t);
    //cout<<endl;

}

bool check(pitem t,int l,int r){
    bool ans=false;
    pitem a1,a2,a3;
    split(t,a2,a3,r+1);
    split(a2,a1,a2,l);
    assert(size(a2)==r+1-l);
    if (mn(a2)==0)ans=true;

    merge(t,a1,a2);
    merge(t,t,a3);
    return ans;
}
string ans;

void answer(pitem t){
    if (!t)return;
    push(t);
    answer(t->l);
    if (t->val==1){
        if (ans.back()=='B')ans+='B';
        else ans+='R';
    }
    else{
        if (ans.back()=='B')ans+='R';
        else ans+='B';
    }
   // cout<<ans<<endl;
    answer(t->r);
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    pitem treap=NULL;
    FOR(i,n-1){
        pb(treap);
    }

    //print(treap);
    //cout<<endl;
    FOR(i,r){
        if (x[i]==1){
            if (a[i]==b[i])continue;
            cutmk(treap,a[i],b[i]-1);
            //print(treap);
            //cout<<endl;
        }
    }
    //print(treap);
    //cout<<endl;
    FOR(i,r){
        if (x[i]==2){
            if (a[i]==b[i]){
                return 0;
            }
            if (!check(treap,a[i],b[i]-1)){
                return 0;
            }
        }
    }
    ans="R";
    answer(treap);
    craft(ans);
    return 1;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 0 / 30