Submission #126596

#	Time	Username	Problem	Language	Result	Execution time	Memory
126596		zozder	Wall (IOI14_wall)	C++14	100 / 100	696 ms	107384 KiB

wall

#include "wall.h"
#include <iostream>
#include <cmath>
#define inf 10000000
#define maxn 4*2000000+5
using namespace std;

int ans[2000005];

struct Tree{
	int mn,mx;
}tree[maxn];

void pushdown(int p)
{
	int sl = 2*p , sr = 2*p+1;
	if(tree[p].mx!=0)//max
	{
		int t = tree[p].mx;
		tree[p].mx = 0;
		tree[sl].mx = max(tree[sl].mx, t);
		tree[sl].mn = max(tree[sl].mn, t);
		tree[sr].mx = max(tree[sr].mx, t);
		tree[sr].mn = max(tree[sr].mn, t);
	}
	if(tree[p].mn!=inf)//min
	{
		int t = tree[p].mn;
		tree[p].mn = inf;
		tree[sl].mx = min(tree[sl].mx, t);
		tree[sl].mn = min(tree[sl].mn, t);
		tree[sr].mx = min(tree[sr].mx, t);
		tree[sr].mn = min(tree[sr].mn, t);
	}
}

void update(int p, int l, int r, int x, int y, int op, int h)
{
	int sl=2*p,sr=2*p+1;
//	cout<<p<<endl;
//	cout<<x<<","<<y<<","<<l<<","<<r<<","<<op<<","<<h<<endl;
	if(x<=l&&r<=y)
	{
//		cout<<x<<","<<y<<","<<l<<","<<r<<","<<op<<","<<h<<endl;
		if(op==1)
		{
			tree[p].mx=max(tree[p].mx, h);
			tree[p].mn=max(tree[p].mn, h);
		}
		if(op==2)
		{
			tree[p].mx=min(tree[p].mx, h);
			tree[p].mn=min(tree[p].mn, h);
		}
//		cout<<p<<","<<tree[p].mx<<","<<tree[p].mn<<","<<h<<endl;
//		cout<<"-------"<<endl;
	}
	else
	{
		pushdown(p);
		if(x<=(l+r)/2)update(sl, l, (l+r)/2, x, y, op, h);
		if((l+r)/2<y)update(sr, (l+r)/2+1, r, x, y, op, h);
	}
}

void put_tree(int p, int l, int r)
{
//	cout<<"l:"<<l<<","<<"r:"<<r<<endl;
	if(l==r)ans[l]=tree[p].mx;
	else
	{
		pushdown(p);
		put_tree(2*p, l, (l+r)/2);
		put_tree(2*p+1, (l+r)/2+1, r);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<maxn;i++)
	{
		tree[i].mx=0;
		tree[i].mn=inf;
	}
	
	for(int i=0;i<k;i++)
	{
//		cout<<"time:"<<i+1<<",op:"<<op[i]<<endl;
		update(1,0,n-1,left[i],right[i],op[i],height[i]);
	}
	
	put_tree(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