Submission #113243

#	Time	Username	Problem	Language	Result	Execution time	Memory
113243		njchung99	Wall (IOI14_wall)	C++14	0 / 100	2 ms	384 KiB

wall

#include "wall.h"
#include<cstdio>
#include<algorithm>
using namespace std;
int mi[8000000], ma[8000000];
int *dap;
void update(int lo, int hi,int val,int node, int x, int y,int p) {
	if (hi < x || y < lo)return;
	if (lo <= x && y <= hi) {
		if (p == 1) {
			mi[node] = max(mi[node], val);
			ma[node] = max(ma[node], val);
		}
		else
		{
			mi[node] = min(mi[node], val);
			ma[node] = min(ma[node], val);
		}
		if (x == y)
			dap[x] = mi[node];
		return;
	}
	int ll = node * 2;
	int rr = node * 2 + 1;
	int mid = (x + y) / 2;
	mi[ll] = min(mi[ll], mi[node]); mi[rr] = min(mi[ll], mi[node]);
	ma[ll] = min(ma[ll], mi[node]); ma[rr] = min(ma[rr], mi[node]);
	mi[ll] = max(mi[ll], ma[node]); mi[rr] = max(mi[rr], ma[node]);
	ma[ll] = max(ma[ll], ma[node]); ma[rr] = max(ma[rr], ma[node]);
	ma[node] = 0; mi[node] = 1234567890;
	update(lo, hi, val, node*2, x, mid, p);
	update(lo, hi, val, node * 2 + 1, mid + 1, y, p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	dap = finalHeight;
	for (int i = 0; i < k; ++i) {
		update(left[i], right[i], height[i], 1, 0, n, op[i]);
	}
	for (int i = 0; i < n; ++i)
		update(i,i,0,1,0,n,0);
	return;
}

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