Submission #377881

#	Time	Username	Problem	Language	Result	Execution time	Memory
377881		YJU	Wall (IOI14_wall)	C++14	100 / 100	1147 ms	171628 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long 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<<60);
#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 node{B.r,B.r};
	}else if(A.r<=B.l){
		return node{B.l,B.l};
	}else{
		assert(max(A.l,B.l)<=min(A.r,B.r));
		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(int n,int k,int op[],int left[],int right[],int height[],int 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);
		}
		finalHeight[i]=seg[1].l;
		for(ll j:rem[i]){
            ins(1,0,k,j,node{0,INF});
		}
	}
	//REP(i,n)cout<<finalHeight[i]<<" \n"[i==n-1];
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    int oper[]={1,2,2,1,1,2};
    int l[]   ={1,4,3,0,2,6};
    int r[]   ={8,9,6,5,2,7};
    int h[]   ={4,1,5,3,5,0};
	int ans[10];
	buildWall(10,6,oper,l,r,h,ans);
	REP(i,10)cout<<ans[i]<<" \n"[i==9];
	return 0;
}
//*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39