| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 472554 | Haidara | Wall (IOI14_wall) | C++17 | 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.
/** * * * * * * * * * * * * * * **\
* *
* Author: Haidara Nassour *
* Coded in: 2021\09\12 HH:MM:SS *
* Lang: C++ *
* *
\** * * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test int tests;cin>>tests;while(tests--)
#define int long long
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ss second
#define pp push_back
#define debug(x) cout<<#x<<" ";
using namespace std;
using namespace __gnu_pbds;
void SIO(string name="")
{
if(name!="")
{
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
}
template <class T> using o_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
///order_of_key = find index of element x ( returned val is integer )
///find_by_order = find value at index x ( returned val is pointer )
const double pi=2.0*acos(0.0);
const int inf=1LL<<62LL;
const int mod=998244353;
const int maxn=2000200;
int n;
struct node
{
int setdown=inf,setup=0,maxtall=inf,mintall=0,last=0;
/// setdown -> all buildings greater than it will equal to it
/// setup -> all buildings smaller than it will equal to it
} st[maxn*4];
bool add=0;
int val;
void pull(int inx,int l,int r)
{
st[inx].mintall=max(st[inx].mintall,st[inx].setup);
st[inx].maxtall=min(st[inx].maxtall,st[inx].setdown);
if(add)
st[inx].last=0;
else
st[inx].last=1;
if(l!=r)
{
st[inx*2].setup=max(st[inx*2].setup,st[inx].setup);
st[inx*2].setdown=min(st[inx*2].setdown,st[inx].setdown);
st[inx*2+1].setup=max(st[inx*2+1].setup,st[inx].setup);
st[inx*2+1].setdown=min(st[inx*2+1].setdown,st[inx].setdown);
}
st[inx].setdown=inf;
st[inx].setup=0;
}
void update(int ul,int ur,int l=1,int r=n,int inx=1)
{
pull(inx,l,r);
if(ul<=l&&r<=ur)
{
/// setdown -> all buildings greater than it will equal to it
/// setup -> all buildings smaller than it will equal to it
if(add)
st[inx].setup=val;
else
st[inx].setdown=val;
pull(inx,l,r);
return ;
}
if(l>ur||ul>r)
return ;
int mid=l+(r-l)/2;
update(ul,ur,l,mid,inx*2);
update(ul,ur,mid+1,r,inx*2+1);
}
int query(int pos,int l=1,int r=n,int inx=1)
{
pull(inx,l,r);
if(l==r)
{
if(!st[inx].last)
return st[inx].mintall;
return st[inx].maxtall;
}
int mid=l+(r-l)/2;
int res;
if(pos<=mid)
res=query(pos,l,mid,inx*2);
else
res=query(pos,mid+1,r,inx*2+1);
}
void buildWall(int sz, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
n=sz;
FOR(i,k)
{
right[i]++;
left[i]++;
add=0;
val=height[i];
if(op[i]==1)
add=1,update(left[i],right[i]);
else
update(left[i],right[i]);
}
FOR(i,n)
finalHeight[i]=query(i+1);
}