Submission #242263

#	Time	Username	Problem	Language	Result	Execution time	Memory
242263		SomeoneUnknown	Jousting tournament (IOI12_tournament)	C++14	0 / 100	47 ms	14968 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);
    }
} *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!
} *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 *rootv;
    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-1);
        int acte = bs(E[i]+1, N-1)-1;
        if(acts >= acte) exit(-1);
        if(rootc->queryr(acts, acte-1) == 0){
            rootv->update(acts, acte);
        }
        rootb->clr(acts+1, acte);
    }
    return rootv->queryf();
}

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