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;
int segm_tree[6000000];
int leftNode(int i)
{
return i*2;
}
int rightNode(int i)
{
return i*2+1;
}
void recompute(int i)
{
segm_tree[i]=max(segm_tree[leftNode(i)],segm_tree[rightNode(i)]);
}
struct bound
{
int on;
int a,b;
} lazy[6000005];
#define inf 1000000
void combine(int cur,int past)
{
if(lazy[cur].on==0){
lazy[cur]=lazy[past];
return;
}
int x=lazy[past].a;
if(x>lazy[cur].a)
lazy[cur].a=x;
if(x>lazy[cur].b)
lazy[cur].b=x;
x=lazy[past].b;
if(x<lazy[cur].a)
lazy[cur].a=x;
if(x<lazy[cur].b)
lazy[cur].b=x;
}
void propagate(int i,int L,int R)
{
if(lazy[i].on==0) return;
segm_tree[i]=max(segm_tree[i],lazy[i].a);
segm_tree[i]=min(segm_tree[i],lazy[i].b);
if(L<R){
combine(leftNode(i),i);
combine(rightNode(i),i);
}
lazy[i].on=0;
lazy[i].a=-inf;
lazy[i].b=inf;
}
void update(int i,int L,int R,int x,int y,int type,int h)
{
propagate(i,L,R);
if(x<=L && R<=y){
if(type==1) lazy[i].a=h,lazy[i].b=inf;
else lazy[i].a=-inf,lazy[i].b=h;
lazy[i].on=1;
}
else{
int mid=(L+R)/2;
if(x<=mid)
update(leftNode(i),L,mid,x,y,type,h);
if(mid+1<=y)
update(rightNode(i),mid+1,R,x,y,type,h);
propagate(leftNode(i),L,mid);
propagate(rightNode(i),mid+1,R);
recompute(i);
}
}
int query(int i,int L,int R,int x)
{
propagate(i,L,R);
if(L==R){
return segm_tree[i];
}
else{
int mid=(L+R)/2;
if(x<=mid)
return query(leftNode(i),L,mid,x);
else
return query(rightNode(i),mid+1,R,x);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++){
update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=query(1,1,n,i+1);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |