Submission #242291

#	Time	Username	Problem	Language	Result	Execution time	Memory
242291		SomeoneUnknown	Jousting tournament (IOI12_tournament)	C++14	100 / 100	649 ms	29816 KiB

tournament

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

struct node{
    int lo, hi, mid, val;
    bool lazyclr;
    node *lft, *rght;
    node(int l, int h){
        lo = l;
        hi = h;
        mid = (l+h)/2;
        val = h-l+1;
        lazyclr = false;
        if(h<l) exit(-1);
        if(l<h){
            lft = new node(l, mid);
            rght = new node(mid+1, h);
        }
    }

    void propogate(){
        if(!lazyclr) return;
        val = 0;
        if(lo<hi){
            lft->lazyclr = true;
            rght->lazyclr = true;
        }
    }

    int query(int l, int h){
        propogate();
        if(l <= lo && h >= hi) return val;
        if(l > mid) return rght->query(l, h);
        if(h <= mid) return lft->query(l, h);
        return lft->query(l, h) + rght->query(l, h);
    }

    void clr(int l, int h){
        propogate();
        if(lazyclr == true) return;
        if(l <= lo && h >= hi){
            lazyclr = true;
            return;
        }
        if(h > mid) rght->clr(l, h);
        if(l <= mid) lft->clr(l, h);
        rght->propogate();
        lft->propogate();
        val = lft->val + rght->val;
    }
} *rootb;

struct nodei{
    int lo, hi, mid, val;
    int lazyclr;
    nodei *lft, *rght;
    nodei(int l, int h){
        lo = l;
        hi = h;
        mid = (l+h)/2;
        val = 0;
        lazyclr = 0;
        if(h<l) exit(-1);
        if(l<h){
            lft = new nodei(l, mid);
            rght = new nodei(mid+1, h);
        }
    }

    void propogate(){
        //if(!lazyclr) return;
        //val = 0;
        if(lo<hi){
            lft->lazyclr += lazyclr;
            rght->lazyclr += lazyclr;
        }
        val += lazyclr;
        lazyclr = 0;
    }

    int queryf(){
        propogate();
        if(lo == hi) return lo;
        lft->propogate();
        rght->propogate();
        if(lft->val < rght->val){
            return rght->queryf();
        }else{
            return lft->queryf();
        }
    }


    int queryr(int l, int h){
        propogate();
        if(l <= lo && h >= hi) return val;
        if(l > mid) return rght->queryr(l, h);
        if(h <= mid) return lft->queryr(l, h);
        return max(lft->queryr(l, h), rght->queryr(l, h));
    }

    void update(int l, int h){
        propogate();
        if(l <= lo && h >= hi){
            ++lazyclr;
            return;
        }
        if(h > mid) rght->update(l, h);
        if(l <= mid) lft->update(l, h);
        lft->propogate();
        rght->propogate();
        val = max(lft->val, rght->val);
    } //write query!
} *rootv, *rootc;

int bs(int no, int n){ //pass in s, e+1.
    int lo = no-1;
    int hi = n;
    while(hi-lo>1){
        int mid = (hi+lo)/2;
        int res = rootb->query(0, mid);
        if(res > no){
            hi = mid;
        }else{
            lo = mid;
        }
    }
    return hi;
}

int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){
    //nodei ;
    rootc = new nodei(0, N-2);
    rootv = new nodei(0, N-1);
    rootb = new node(0, N-1);
    for(int i = 0; i < N-1; i++){
        if(K[i] > R){
            rootc->update(i,i);
        }
    }
    for(int i = 0; i < C; ++i){
        int acts = bs(S[i], N);
        int acte = bs(E[i]+1, N)-1;
        if(acts >= acte) exit(-1);
        int res = rootc->queryr(acts, acte-1);
        //printf("QUERY: %d to %d. RES: %d.\n",acts, acte-1, res);
        if(res == 0){
            rootv->update(acts, acte);
        }
        rootb->clr(acts+1, acte);
        //printf("rootb status: ");
        for(int j = 0; j < N; j++){
            //printf("%d", rootb->query(0,j));
        }
        //printf("\n"); //*/
    }
    return rootv->queryf();
}

/*int main(){
    int n, c, r;
    scanf("%d %d %d", &n, &c, &r);
    int k[n-1];
    int s[c], e[c];
    for(int i = 0; i < n-1; i++){
        scanf("%d", &k[i]);
    }
    for(int i = 0; i < c; i++){
        scanf("%d %d", &s[i], &e[i]);
    }
    printf("%d\n", GetBestPosition(n,c,r,k,s,e));
    printf("\n");
    for(int i = 0; i < n; i++){
        printf("%d\n", rootv->queryr(i,i));
    }
    printf("\n");
    for(int i = 0; i < n-1; i++){
        printf("%d\n", rootc->queryr(i,i));
    }
}//*/
/*
5 2 3
1 0 2 4
1 3
0 2
*/

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51