이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |