# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377867 | YJU | 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>
#include"wall.h"
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<29);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
struct node{
ll l,r;
}seg[4*N];
node operator +(node A,node B){
if(A.l>=B.r){
return B;
}else if(A.r<=B.l){
return B;
}else{
return node{max(A.l,B.l),min(A.r,B.r)};
}
}
void ins(ll id,ll l,ll r,ll to,node del){
if(l==r-1){seg[id]=del;return ;}
ll mid=(l+r)>>1;
if(to<mid){
ins(id*2,l,mid,to,del);
}else{
ins(id*2+1,mid,r,to,del);
}
seg[id]=seg[id*2]+seg[id*2+1];
}
vector<ll> app[N],rem[N];
void buildWall(ll n,ll k,vector<ll> op,vector<ll> left,vector<ll> right,vector<ll> height,vector<ll> &finalHeight){
REP(i,k){
ins(1,0,k,i,node{0,INF});
app[left[i]].pb(i);
rem[right[i]].pb(i);
}
REP(i,n){
for(ll j:app[i]){
node tmp;
if(op[j]==1)tmp=node{height[j],INF};
else tmp=node{0,height[j]};
ins(1,0,k,j,tmp);
}
for(ll j:rem[i]){
ins(1,0,k,j,node{0,INF});
}
finalHeight[i]=seg[1].l;
}
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
return 0;
}
*/