Submission #373392

#	Time	Username	Problem	Language	Result	Execution time	Memory
373392		Atill83	Deda (COCI17_deda)	C++14	20 / 140	216 ms	4204 KiB

deda

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, q;

struct item {
    int val, pri, ans, binme;

    item * l, *r;

    void init(int vl, int bine){
        val = vl;
        binme = bine;
        ans = bine;
        pri = (((1LL * rand())<<16)%mod + rand()) % mod;
        l = NULL, r = NULL;  
    }
};

typedef item * pitem;

int value(pitem a){
    if(a == NULL)
        return mod;
    return a->binme;
}

void calc(pitem a){
    a->ans = min({value(a), value(a->l), value(a->r)});
}


void split(pitem v, pitem & left, pitem & right, int key){
    if(v == NULL){
        left = NULL;
        right = NULL;
        return;
    }
    if(v->val < key){
        split(v->r, v->r, right, key);
        left = v;
    }else{
        split(v->l, left, v->l, key);
        right = v;
    }
    calc(v);
}

void merge(pitem & v, pitem left, pitem right){
    if(left != NULL && right != NULL)
        assert((left->val) < (right->val));
    if(left == NULL)
        v = right;
    else if(right == NULL)
        v = left;
    else if(left->pri > right->pri){
        merge(left->r, left->r, right);
        v = left;
    }else{
        merge(right->l, left, right->l);
        v = right;
    }
    calc(v);
}

int clc(pitem v, int x){
    if(v == NULL)
        return mod;
    if(v->l == NULL && v->r == NULL)
        return v->val;
    if(v->l != NULL && v->l->ans <= x){
        return clc(v->l, x);
    }else if(v->binme <= x){
        return v->val;
    }else{
        return clc(v->r, x);
    }
}

void print(pitem a){
    if(a == NULL)
        return;
    print(a->l);
    cout<<(a->val)<<" ";
    print(a->r);
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif
    srand(time(NULL));
    cin>>n>>q;


    pitem root = new item;

    root->init(n + 1, 0);
    while(q--){
        char ty;
        cin>>ty;
        if(ty == 'D'){
            int y, b;
            cin>>y>>b;

            /*if(q == 0){
                cout<<"BAS"<<endl;
                print(root);
                cout<<endl;
            }*/

            pitem l, r;
            split(root, l, r, b);
            
            /*if(q == 0){
                cout<<"left :"<<endl;
                print(l);
                cout<<endl<<"right:"<<endl;
                print(r);
                cout<<endl;
            }*/
            int cev = clc(r, y);
            cout<<(cev == n + 1 ? -1 : cev)<<endl;
            merge(root, l, r);

            /*if(q == 0){
                cout<<"SON"<<endl;
                print(root);
                cout<<endl;
            }*/
        }else{
            int x, a;   
            cin>>x>>a;
            pitem v = new item;
            v->init(a, x);

            pitem l, r;
            split(root, l, r, a);
            merge(root, l, v);
            merge(root, root, r);
        }
    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 20 / 140