Submission #667807

#	Time	Username	Problem	Language	Result	Execution time	Memory
667807		Baytoro	Wall (IOI14_wall)	C++17	100 / 100	542 ms	77388 KiB

wall

#include "bits/stdc++.h"
//#include "grader.cpp"
#include "wall.h"
using namespace std;
//#define int long long
#define fr first
#define sc second
const int INF=1e9+17,mod=1e9+7;
const int N=2e6+5;
pair<int,int> st[4*N]; 
int ans[N];
pair<int,int> f(pair<int,int> a, pair<int,int> b){
	if(a.sc<b.fr)
		return {a.sc,a.sc};
	if(a.fr>b.sc)
		return {a.fr,a.fr};
	return {max(a.fr,b.fr),min(a.sc,b.sc)};
}
void push(int x){
	if(st[x]!=make_pair(-INF,INF)){
		st[2*x]=f(st[x],st[2*x]);
		st[2*x+1]=f(st[x],st[2*x+1]);
		st[x]={-INF,INF};
	}
}
void update(int x, int l, int r, int lx, int rx, pair<int,int> v){
	if(l>rx || r<lx) return;
	if(lx<=l && r<=rx){
		st[x]=f(v,st[x]);
		return;
	}
	if(l!=r) push(x);
	int md=(l+r)/2;
	update(2*x,l,md,lx,rx,v);
	update(2*x+1,md+1,r,lx,rx,v);
}
void get(int x, int l, int r){
	if(l==r){
		ans[l]=st[x].fr;
		return;
	}
	push(x);
	int md=(l+r)/2;
	get(2*x,l,md);
	get(2*x+1,md+1,r);
}
int n,k;
void init(int x=1, int l=0, int r=n-1){
	if(l==0 && r==n-1)
		st[x]={0,0};
	else
		st[x]={-INF,INF};
	if(l==r) return;
	int md=(l+r)/2;
	init(2*x,l,md);
	init(2*x+1,md+1,r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
	n=N;
	k=K;
	init();
	for(int i=0;i<k;i++){
		pair<int,int> a={-INF,INF};
		if(op[i]==1)
			a.fr=height[i];
		else
			a.sc=height[i];
		update(1,0,n-1,left[i],right[i],a);
	}
	get(1,0,n-1);
	for(int i=0;i<n;i++)
		finalHeight[i]=ans[i];
}

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