| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 597608 | enerelt14 | 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;
struct node{
int lazy, mn, mx;
node(){
lazy=-1;
mn=0;
mx=0;
}
};
node tree[8000005];
void propagate(int id, int l, int r){
if (l==r)return;
if (tree[id].lazy!=-1){
tree[id*2+1].lazy=tree[id].lazy;
tree[id*2+2].lazy=tree[id].lazy;
tree[id*2+1].mn=tree[id].lazy;
tree[id*2+2].mn=tree[id].lazy;
tree[id*2+1].mx=tree[id].lazy;
tree[id*2+2].mx=tree[id].lazy;
}
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
tree[id].lazy=-1;
}
void update(int x, int id, int l, int r, int L, int R, int h){
if (l>R || L>r)return;
if (!x && tree[id].mn>=h)return;
if (x && tree[id].mx<=h)return;
propagate(id, l, r);
if (L<=l && r<=R){
if (x){
tree[id].lazy=min(tree[id].lazy, h);
tree[id].mx=min(tree[id].mx, h);
tree[id].mn=min(tree[id].mn, h);
}
else{
tree[id].lazy=max(tree[id].lazy, h);
tree[id].mx=max(tree[id].mx, h);
tree[id].mn=max(tree[id].mn, h);
}
return;
}
int mid=(l+r)/2;
update(x, id*2+1, l, mid, L, R, h);
update(x, id*2+2, mid+1, r, L, R, h);
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
int find(int id, int l, int r, int i){
propagate(id, l, r);
if (l==r)return tree[id].mn;
int mid=(l+r)/2;
if (mid<i)return find(id*2+2, mid+1, r, i);
else return find(id*2+1, l, mid, i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0;i<4*n;i++)lazy[i]=-1;
for (int i=1;i<=k;i++){
update(op[i]-1, 0, 0, n-1, left[i], right[i], height[i]);
}
for (int i=0;i<n;i++)finalHeight[i]=find(0, 0, n-1, i);
return;
}