Submission #416131

#	Time	Username	Problem	Language	Result	Execution time	Memory
416131		xyzyzl	Wall (IOI14_wall)	C++14	100 / 100	1267 ms	93868 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);
		}
		return;
	}
	int mid = (l+r)/2;
	// nothing that could go wrong here, this is just checking the smaller intervals
	// individually with no deeper recursion
	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;
	// here is what is wrong
	// we are cutting our current interval into intervals based on mid, and then 
	// we process updates for each interval
	if(b <= mid)
	{
		upd(2*node, a, b, mn, mx, l, mid);
	} else if(a > mid)
	{
		upd(2*node+1, a, b, mn, mx, mid+1, r);
	} else 
	{
		upd(2*node, a, mid, mn, mx, l, mid);
		upd(2*node+1, mid+1, b, mn, mx, 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];		
		return;
	}
	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];
}

/*
int main()
{
	int op[6] = {1,2,2,1,1,2};
	int left[6] = {1,4,3,0,2,6};
	int right[6] = {8,9,6,5,2,7};
	int height[6] = {4,1,5,3,5,0};
	int finalHeight[10] = {0,0,0,0,0,0,0,0,0,0};
	buildWall(10, 6, op, left, right, height, finalHeight);
	for(int i = 0; i < 10; i++)
	{
		cout << finalHeight[i] << " ";
	}
}
*/

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