Submission #902365

#	Time	Username	Problem	Language	Result	Execution time	Memory
902365		UmairAhmadMirza	Wall (IOI14_wall)	C++17	100 / 100	716 ms	99428 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
int const N=2e6+5;
int const inf=1e5;
int rise[4*N];
int down[4*N];
void up_to_date(int node,int l,int r){
	if(l+1==r)
		return;
	if(rise[node]>0){
		int h=rise[node];
		rise[node]=0;
		rise[node*2]=max(h,rise[node*2]);
		down[node*2]=max(down[node*2],rise[node*2]);
		rise[node*2+1]=max(h,rise[node*2+1]);
		down[node*2+1]=max(down[node*2+1],rise[node*2+1]);
	}
	if(down[node]<inf){
		int h=down[node];
		down[node]=inf;
		if(l+1<r){
			down[node*2]=min(h,down[node*2]);
			rise[node*2]=min(rise[node*2],down[node*2]);
			down[node*2+1]=min(h,down[node*2+1]);
			rise[node*2+1]=min(rise[node*2+1],down[node*2+1]);
		}
	}
}
void update(int node,int s,int e,int l,int r,int h,int t){
	if(e<=l || r<=s)
		return;
	// cout<<node<<' '<<s<<' '<<e-1<<endl;
	// cout<<rise[node]<<' '<<down[node]<<endl;
	up_to_date(node,s,e);
	if(l<=s && e<=r){
		if(t==1){
			rise[node]=max(h,rise[node]);
			down[node]=max(down[node],rise[node]);
		}
		else{
			down[node]=min(h,down[node]);
			rise[node]=min(rise[node],down[node]);
		}
		// cout<<"leave"<<endl;
		// cout<<rise[node]<<' '<<down[node]<<endl;
		// cout<<endl;
	}
	else{
		int mid=(s+e)/2;
		update(node*2,s,mid,l,r,h,t);
		update(node*2+1,mid,e,l,r,h,t);
	}
}
void printing(int node,int l,int r){
	// cout<<"**"<<endl;
	// cout<<l<<' '<<r-1<<endl;
	// cout<<rise[node]<<' '<<down[node]<<endl;
	if(l+1==r)
		return;
	int mid=(l+r)/2;
	printing(node*2,l,mid);
	printing(node*2+1,mid,r);
}
int query(int node,int s,int e,int p){
	up_to_date(node,s,e);
	if(s+1==e)
		return rise[node];
	int mid=(s+e)/2;
	if(p<mid)
		return query(node*2,s,mid,p);
	else
		return query(node*2+1,mid,e,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < 4*N; ++i){
		down[i]=inf;
		rise[i]=0;
	}
	for (int i = 0; i < k; ++i){
		// cout<<endl;
		update(1,0,n,left[i],right[i]+1,height[i],op[i]);
// 		printing(0,0,n);
	}
	for (int i = 0; i < n; ++i)
		finalHeight[i]=query(1,0,n,i);
}

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