| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 889009 | BBart888 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN= 2e6+11;
int tmx[4*MAXN];
int tmn[4*MAXN];
pair<int,int> lazy[4*MAXN];
void pull_add(int x,int val)
{
tmx[x] = max(tmx[x],val);
tmn[x] = max(tmn[x],val);
lazy[x].first = max(lazy[x].first,val);
lazy[x].second = max(lazy[x].second,val);
}
void pull_dec(int x,int val)
{
tmx[x] = min(tmx[x],val);
tmn[x] = min(tmn[x],val);
lazy[x].first = min(lazy[x].first,val);
lazy[x].second = min(lazy[x].second,val);
}
void push(int x)
{
if(lazy[x].first != -1e9)
{
pull_add(2*x,lazy[x].first);
pull_add(2*x+1,lazy[x].first);
}
else if(lazy[x].second != 1e9)
{
pull_dec(2*x,lazy[x].second);
pull_dec(2*x+1,lazy[x].second);
}
lazy[x] = {-1e9,1e9};
}
void upd(int v,int tl,int tr,int l,int r,int type,int val)
{
if(l > r)
return;
if(l == tl && tr ==r)
{
if(type == 1)
pull_add(v,val);
else
pull_dec(v,val);
return;
}
int tm =(tl+tr)/2;
push(v);
upd(2*v,tl,tm,l,min(r,tm),type,val);
upd(2*v+1,tm+1,tr,max(l,tm+1),r,type,val);
tmx[v] = max(tmx[2*v],tmx[2*v+1]);
tmn[v] = min(tmn[2*v],tmn[2*v+1]);
}
int get(int v,int tl,int tr,int pos)
{
if(tl == tr)
return tmx[v];
int tm =(tl+tr)/2;
push(v);
if(pos <= tm)
return get(2*v,tl,tm,pos);
else
return get(2*v+1,tm+1,tr,pos);
}
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)
upd(1,0,MAXN,left[i],right[i],1,height[i]);
else
upd(1,0,MAXN,left[i],right[i],0,height[i]);
}
for(int i =0;i<n;i++)
finalHeight[i] = get(1,0,MAXN,i);
}
int main()
{
cin.tie(0);
cout.tie(0);
/*
upd(1,0,MAXN,1,5,1,6);
upd(1,0,MAXN,4,5,0,3);
for(int i =0;i<=10;i++)
cout<<get(1,0,MAXN,i)<<" ";
*/
return 0;
}