제출 #242291

#제출 시각아이디문제언어결과실행 시간메모리
242291SomeoneUnknown마상시합 토너먼트 (IOI12_tournament)C++14
100 / 100
649 ms29816 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...