Submission #703331

#	Time	Username	Problem	Language	Result	Execution time	Memory
703331		jamezzz	Wall (IOI14_wall)	C++17	61 / 100	1171 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
#define all(x) x.begin(),x.end()
#define maxn 2000005
#define INF 1023456789

struct node{
	int s,e,m,mn,mx,lzmn,lzmx;//value has to between [mn, mx];
	node *l=NULL,*r=NULL;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,mn=0,mx=INF,lzmn=0,lzmx=INF;
	}
	void create(){
		if(l!=NULL)return;
		l=new node(s,m);
		r=new node(m+1,e);
		l->mn=r->mn=mn;
		l->mx=r->mx=mx;
	}
	ii join(ii l,ii r){
		auto[lmn,lmx]=l;
		auto[rmn,rmx]=r;
		if(max(lmn,rmn)<=min(lmx,rmx))return {max(lmn,rmn),min(lmx,rmx)};
		else if(rmx<=lmn)return {rmx,rmx};
		else return {rmn,rmn};
	}
	void ppo(){
		tie(mn,mx)=join({mn,mx},{lzmn,lzmx});
		if(s!=e){
			create();
			tie(l->lzmn,l->lzmx)=join({l->lzmn,l->lzmx},{lzmn,lzmx});
			tie(r->lzmn,r->lzmx)=join({r->lzmn,r->lzmx},{lzmn,lzmx});
		}
		lzmn=0,lzmx=INF;
	}
	void up(int x,int y,int type,int h){
		if(s==x&&e==y){
			if(type==1)tie(lzmn,lzmx)=join({lzmn,lzmx},{h,INF});
			else tie(lzmn,lzmx)=join({lzmn,lzmx},{0,h});
			return;
		}
		create();ppo();
		if(y<=m)l->up(x,y,type,h);
		else if(x>m)r->up(x,y,type,h);
		else{
			l->up(x,m,type,h);
			r->up(m+1,y,type,h);
		}
		l->ppo(),r->ppo();
		tie(mn,mx)=join({l->mn,l->mx},{r->mn,r->mx});
	}
	ii qry(int x){
		create();ppo();
		if(s==x&&e==x)return {mn,mx};
		if(x<=m)return l->qry(x);
		else return r->qry(x);
	}
}*rt;

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	rt=new node(0,n-1);
	for(int i=0;i<k;++i){
		rt->up(left[i],right[i],op[i],height[i]);		
	}
	for(int i=0;i<n;++i){
		finalHeight[i]=rt->qry(i).first;
	}
}

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