| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 333479 | wildturtle | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector < pair < long long, long long > > tree;
void apply(long long node,long long L,long long R) {
tree[node].first=max(min(tree[node].first,R),L);
tree[node].second=max(min(tree[node].second,R),L);
}
void push(long long node,long long le,long long ri) {
if(le<ri) {
apply(2*node,tree[node].first,tree[node].second);
apply(2*node+1,tree[node].first,tree[node].second);
}
tree[node].second=1e9+3;
tree[node].first=0;
}
void go(long long node,long long le,long long ri,long long finalHeight[]) {
if(le==ri) { finalHeight[le]=tree[node].first; return; }
push(node,le,ri);
go(2*node,le,(le+ri)/2,finalHeight);
go(2*node+1,(le+ri)/2,ri,finalHeight);
}
void update(long long node,long long le,long long ri,long long start,long long end,long long cur1,long long cur2) {
if(ri<start || le>end) return;
if(start<=le && ri<=end) { apply(node,cur1,cur2); return; }
push(node,le,ri);
update(2*node,le,(le+ri)/2,start,end,cur1,cur2);
update(2*node+1,(le+ri)/2,ri,start,end,cur1,cur2);
}
void buildWall(long long n,long long k,long long op[],long long left[],long long right[],long long height[],long long finalHeight[]) {
tree.resize(4*n+1);
for(long long i=1;i<=k;i++) {
if(op[i]==1) update(1,1,n,left[i],right[i],height[i],1e9+5);
else update(1,1,n,left[i],right[i],-(1e9+5),height[i]);
}
go(1,1,n,finalHeight);
}