| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 347122 | ogibogi2004 | 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;
const int MAXN=2e6;
const int INF=2e8;
struct node
{
int down,up;
node()
{
down=INF;up=0;
}
};
node tree[4*MAXN];
node update_d(node t,int h)
{
t.down=min(t.down,h);
t.up=min(t.up,t.down);
return t;
}
node update_u(node t,int h)
{
t.up=max(t.up,h);
t.down=max(t.down,t.up);
return t;
}
node update(node t1,node t2)
{
t1.down=min(t1.down,t2.down);
t1.up=max(t1.up,t2.up);
t1.down=max(t1.down,t2.up);
t1.up=min(t1.up,t2.down);
return t1;
}
void push(int l,int r,int idx)
{
if(tree[idx].down==INF&&tree[idx].up==0)return;
if(l==r)return;
tree[idx*2]=update(tree[idx*2],tree[idx]);
tree[idx*2+1]=update(tree[idx*2+1],tree[idx]);
tree[idx]={INF,0};
}
void update_d(int idx,int l,int r,int ql,int qr,int h)
{
push(l,r,idx);
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx]=update_d(tree[idx],h);
push(l,r,idx);
return;
}
int mid=(l+r)/2;
update_d(idx*2,l,mid,ql,qr,h);
update_d(idx*2+1,mid+1,r,ql,qr,h);
}
void update_u(int idx,int l,int r,int ql,int qr,int h)
{
push(l,r,idx);
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx]=update_u(tree[idx],h);
push(l,r,idx);
return;
}
int mid=(l+r)/2;
update_u(idx*2,l,mid,ql,qr,h);
update_u(idx*2+1,mid+1,r,ql,qr,h);
}
int ans1[4*MAXN];
void trav(int idx,int l,int r)
{
push(l,r,idx);
//cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
if(l==r)
{
ans1[l]=min(tree[idx].down,tree[idx].up);
}
else
{
int mid=(l+r)/2;
trav(idx*2,l,mid);
trav(idx*2+1,mid+1,r);
}
}
void trav1(int idx,int l,int r)
{
cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
//push(l,r,idx);
if(l==r)
{
return;
}
else
{
int mid=(l+r)/2;
trav1(idx*2,l,mid);
trav1(idx*2+1,mid+1,r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++)
{
if(op[i]==1)
{
update_u(1,0,n-1,left[i],right[i],height[i]);
}
else
{
update_d(1,0,n-1,left[i],right[i],height[i]);
}
//trav1(1,0,n-1);
//cout<<"---------------\n";
}
trav(1,0,n-1);
for(int i=0;i<n;i++)finalHeight[i]=ans1[i];
}