oj.uz

답안 #242291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242291 2020-06-27T08:19:36 Z SomeoneUnknown 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 649 ms 29816 KB 
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 24 ms 1792 KB Output is correct
3 Correct 7 ms 1792 KB Output is correct
4 Correct 22 ms 1792 KB Output is correct
5 Correct 21 ms 1664 KB Output is correct
6 Correct 17 ms 1792 KB Output is correct
7 Correct 23 ms 1792 KB Output is correct
8 Correct 24 ms 1792 KB Output is correct
9 Correct 8 ms 1792 KB Output is correct
10 Correct 24 ms 1792 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 14968 KB Output is correct
2 Correct 649 ms 29688 KB Output is correct
3 Correct 88 ms 28920 KB Output is correct
4 Correct 612 ms 29732 KB Output is correct
5 Correct 616 ms 28616 KB Output is correct
6 Correct 525 ms 29608 KB Output is correct
7 Correct 636 ms 29688 KB Output is correct
8 Correct 635 ms 29816 KB Output is correct
9 Correct 85 ms 29048 KB Output is correct
10 Correct 108 ms 29000 KB Output is correct