Submission #1235900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235900		MasterDebater	Wall (IOI14_wall)	C++20	0 / 100	437 ms	106760 KiB

wall

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define F first
#define S second.first
#define T second.second
const int N=2e6+10,off=(1<<21);
const piii stan={-1,{0,1e9+10}};
piii tour[4*off+5];
pii ans[N];
piii Merge(piii m1,piii m2){
	if(m1.F>m2.F)swap(m1,m2);
	if(m2.T<m1.S)return {m2.F,{m2.T,m2.T}};
	if(m2.S>m1.T)return {m2.F,{m2.S,m2.S}};
	return {m2.F,{max(m1.S,m2.S),min(m1.T,m2.T)}};
}
void update(int x,int y,int l,int r,int node,piii val){
	if(r<x or l>y)return;
	if(x<=l and r<=y){
		tour[node]=Merge(tour[node],val);
		return;
	}
	tour[node*2]=Merge(tour[node*2],tour[node]);
	tour[node*2+1]=Merge(tour[node*2+1],tour[node]);
	update(x,y,l,(l+r)/2,node*2,val);
	update(x,y,(l+r)/2+1,r,node*2+1,val);
	return;
}
void query(int x,int y,int l,int r,int node){
	if(l>y)return;
	if(l==r){
		ans[l]={tour[node].S,tour[node].T};
		return;
	}
	tour[node*2]=Merge(tour[node*2],tour[node]);
	tour[node*2+1]=Merge(tour[node*2+1],tour[node]);
	
	tour[node]=stan;
	query(x,y,l,(l+r)/2,node*2);
	query(x,y,(l+r)/2+1,r,node*2+1);
	return;
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<4*off+5;i++)tour[i]=stan;
	for(int i=0;i<k;i++){
		if(op[i]==1)update(left[i],right[i],0,off-1,1,{i+1,{height[i],1e9+10}});
		else update(left[i],right[i],0,off-1,1,{i+1,{0,height[i]}});
	}
	query(0,n-1,0,off-1,1);
	for(int i=0;i<n;i++){
		finalHeight[i]=max(finalHeight[i],ans[i].first);
		finalHeight[i]=min(finalHeight[i],ans[i].second);
	}
	return;
}

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