Submission #415353

#	Time	Username	Problem	Language	Result	Execution time	Memory
415353		xyzyzl	Wall (IOI14_wall)	C++14	0 / 100	8 ms	844 KiB

wall

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6+5;
const int INF  = 1e9+7;
int n, arr[MAXN], st[4*MAXN], lz1[4*MAXN], lz2[4*MAXN];

void upd(int node, int a, int b, int mn, int mx, int l, int r)
{
	if(l == a && r == b)
	{
		st[node] = max(st[node], mx);
		st[node] = min(st[node], mn);
		if(mx > lz1[node])
		{
			lz1[node] = lz2[node] = mx;
		} else if(mn < lz2[node])
		{
			lz1[node] = lz2[node] = mn;
		} else 
		{
			lz1[node] = min(lz1[node], mn);
			lz2[node] = max(lz2[node], mx);
		}
	}
	int mid = (l+r)/2;
	upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
	upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
	lz1[node] = INF;
	lz2[node] = 0;
	if(b <= mid)
	{
		upd(a, b, mn, mx, 2*node, l, mid);
	} else if(a > mid)
	{
		upd(a, b, mn, mx, 2*node+1, mid+1, r);
	} else 
	{
		upd(a, mid, mn, mx, 2*node, l, mid);
		upd(mid+1, b, mn, mx, 2*node+1, mid+1, r);
	}
	st[node] = min(st[2*node], st[2*node+1]);
}

void build(int node, int l, int r)
{
	if(l == r)
	{
		lz1[node] = INF;
		return;
	}
	int mid = (l+r)/2;
	build(node*2, l, mid);
	build(node*2+1, mid+1, r);
	lz1[node] = INF;
}

void convert(int node, int l, int r)
{
	if(l == r)
	{
		arr[l] = st[node];		
	}
	int mid = (l+r)/2;
	upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
	upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
	lz1[node] = INF;
	lz2[node] = 0;

	convert(2*node, l, mid);
	convert(2*node+1, mid+1, r);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	n = _n;
	build(1, 0, n-1);
	// perform updates for each query.
	for(int i = 0; i < k; i++)
	{
		if(op[i] == 1)
		{
			upd(1, left[i], right[i], INF, height[i], 0, n-1);
		} else 
		{
			upd(1, left[i], right[i], height[i], 0, 0, n-1);
		}
	}
	convert(1, 0, n-1);
	for(int i = 0; i < n; i++) finalHeight[i] = arr[i];
}

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