| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 205073 | awlintqaa | 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 <bits/stdc++.h>
using namespace std;
#define sqr 200
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 2e9;
const ld pai=acos(-1);
#include "wall.h"
int tree[8000009];
struct xxx{int on,mx,mn;}lzy[800009];
void fill(int past,int cur){
if(lzy[node].on==0){
lzy[node]=lzy[pre];
return ;
}
int x=lzy[past].a;
if(x>lzy[cur].a)
lzy[cur].a=x;
if(x>lzy[cur].b)
lzy[cur].b=x;
x=lzy[past].b;
if(x<lzy[cur].a)
lzy[cur].a=x;
if(x<lzy[cur].b)
lzy[cur].b=x;
}
void lzyUPD(int node,int l,int r){
if(lzy[node].on==0)return;
tree[node]=max(tree[node],lzy[node].mn);
tree[node]=min(tree[node],lzy[node].mx);
if(l!=r){
fill(node,node*2);
fill(node,node*2+1);
}
lzy[node].on=0;
lzy[node].mn=-inf;
lzy[node].mx=inf;
}
void upd(int node,int l,int r,int s,int e,int val,int t){
lzyUPD(node,l,r);
if(s>r || e<l)return ;
if(s<=l && e>=r){
if(t==1)lzy[node].mn=val,lzy[node].mx=inf;
else lzy[node].mn=-inf,lzy[node].mx=val;
lzy[node].on=1;
lzyUPD(node,l,r);
return ;
}
upd(node*2,l,mid,s,e,val,t);
upd(node*2+1,mid+1,r,s,e,val,t);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int l,int r,int id){
lzyUPD(node,l,r);
if(l==r)return tree[node];
if(id<=mid)return query(node*2,l,mid,id);
return query(node*2+1,mid+1,r,id);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++)upd(1,0,n-1,left[i],right[i],height[i],op[i]);
for(int i=0;i<n;i++)finalHeight[i]=query(1,0,n-1,i);
}