Submission #373461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373461	2021-03-04T17:28:01 Z	Atill83	Deda (COCI17_deda)	C++14	140 / 140	286 ms	6456 KB

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, ans, binme;
    ll pri;
    item * l, *r;

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

typedef item * pitem;

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

void calc(pitem a){
    if(a == NULL)
        return;
    a->ans = min({a->binme, 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);
    calc(left);
    calc(right);
}

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);
    calc(left);
    calc(right);
}

int clc(pitem v, int x){
    assert(v != NULL);
    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;

            pitem l, r;
            split(root, l, r, b);
            
            int cev = clc(r, y);
            cout<<(cev == n + 1 ? -1 : cev)<<endl;
            merge(root, l, r);
        }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

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	4 ms	492 KB	Output is correct
4	Correct	133 ms	3820 KB	Output is correct
5	Correct	286 ms	6456 KB	Output is correct
6	Correct	265 ms	5996 KB	Output is correct
7	Correct	264 ms	5724 KB	Output is correct