Submission #1042369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042369		pedroslrey	Wall (IOI14_wall)	C++14	100 / 100	598 ms	84564 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int MAXN = 2e6 + 10;

int mx[4*MAXN], mn[4*MAXN];

void add(int pos, int maxi, int mini) {
	if (mx[pos] > mini) 
		mx[pos] = mn[pos] = mini;
	else if (mn[pos] < maxi)
		mx[pos] = mn[pos] = maxi;
	else {
		mx[pos] = max(mx[pos], maxi);
		mn[pos] = min(mn[pos], mini);
	}
}

void refresh(int pos, int ini, int fim) {
	if (ini != fim) {
		add(2*pos, mx[pos], mn[pos]);
		add(2*pos + 1, mx[pos], mn[pos]);
		mx[pos] = 0;
		mn[pos] = 1e9;
	}
}

void update(int pos, int ini, int fim, int l, int r, int maxi, int mini) {
	refresh(pos, ini, fim);
	if (l <= ini && fim <= r) {
		add(pos, maxi, mini);
		refresh(pos, ini, fim);

		return;
	}
	if (r < ini || fim < l) return;

	int m = (ini + fim)/2;
	update(2*pos, ini, m, l, r, maxi, mini);
	update(2*pos + 1, m + 1, fim, l, r, maxi, mini);
}

void build(int pos, int ini, int fim, int ans[]) {
	if (ini == fim) {
		ans[ini] = mx[pos];
		return;
	}

	refresh(pos, ini, fim);
	int m = (ini + fim)/2;
	build(2*pos, ini, m, ans);
	build(2*pos + 1, m + 1, fim, ans);
}

void buildWall(int n, int q, int ops[], int ls[], int rs[], int hs[], int ans[]) {
	for (int i = 1; i <= 4*n; ++i)
		mn[i] = 1e9;

	for (int i = 0; i < q; ++i) 
		if (ops[i] == 1) update(1, 0, n-1, ls[i], rs[i], hs[i], 1e9);
		else update(1, 0, n-1, ls[i], rs[i], 0, hs[i]);

	build(1, 0, n-1, ans);
}

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