Submission #399606

#	Time	Username	Problem	Language	Result	Execution time	Memory
399606		Jasiekstrz	Wall (IOI14_wall)	C++17	100 / 100	768 ms	69672 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;
const int N=2e6,K=5e5,MN=0,MX=1e5;
const int P=21e5;
int pot;
pair<int,int> tree[2*P+10];
void merge(pair<int,int> &x,pair<int,int> y)
{
	if(y.se<x.fi)
		x={y.se,y.se};
	else if(x.se<y.fi)
		x={y.fi,y.fi};
	else
	{
		x.fi=max(x.fi,y.fi);
		x.se=min(x.se,y.se);
	}
	return;
}
void push_down(int i)
{
	merge(tree[2*i],tree[i]);
	merge(tree[2*i+1],tree[i]);
	tree[i]={MN,MX};
	return;
}
void add_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
	if(r<ls || rs<l)
		return;
	else if(ls<=l && r<=rs)
	{
		merge(tree[i],c);
		return;
	}
	push_down(i);
	int mid=(l+r)/2;
	add_t(2*i,l,mid,ls,rs,c);
	add_t(2*i+1,mid+1,r,ls,rs,c);
	return;
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tree[i]={MN,MX};
	for(int i=0;i<k;i++)
	{
		if(op[i]==1) // adding phase
			add_t(1,1,pot,left[i]+1,right[i]+1,{height[i],MX});
		else // removing phase
			add_t(1,1,pot,left[i]+1,right[i]+1,{MN,height[i]});
	}
	for(int i=1;i<pot;i++)
		push_down(i);
	for(int i=0;i<n;i++)
		finalHeight[i]=tree[i+pot].fi;
	return;
}

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