Submission #703333

#	Time	Username	Problem	Language	Result	Execution time	Memory
703333		jamezzz	Wall (IOI14_wall)	C++17	100 / 100	1251 ms	124688 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 disc(d) sort(all(d));d.resize(unique(all(d))-d.begin());
#define maxn 2000005
#define INF 1023456789
 
struct node{
	int s,e,m,mn,mx,lzmn,lzmx;//value has to between [mn, mx];
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,mn=0,mx=INF,lzmn=0,lzmx=INF;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	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){
			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){
		ppo();
		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;
		}
		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){
		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[]){
	vector<int> d;
	for(int i=0;i<k;++i)d.push_back(left[i]),d.push_back(right[i]+1);
	disc(d);
	rt=new node(0,d.size()-1);
	for(int i=0;i<k;++i){
		int l=lower_bound(all(d),left[i])-d.begin();
		int r=lower_bound(all(d),right[i]+1)-d.begin();
		rt->up(l,r-1,op[i],height[i]);
	}
	vector<int> ans;
	ans.resize(d.size(),0);
	for(int i=0;i<d.size();++i){
		ans[i]=rt->qry(i).first;
	}
	d.push_back(n+1);
	for(int i=0;i<d.size()-1;++i){
		int l=d[i],r=d[i+1]-1;
		for(int j=l;j<=r;++j)finalHeight[j]=ans[i];
	}
}
 

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<d.size();++i){
      |              ~^~~~~~~~~
wall.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<d.size()-1;++i){
      |              ~^~~~~~~~~~~

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