oj.uz

Submission #337896

# Submission time Handle Problem Language Result Execution time Memory
337896 2020-12-22T05:17:48 Z Azimjon Wall (IOI14_wall) C++17
100 / 100
 1251 ms 67436 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 1e9;
const int N = 2e6 + 10;

int ka[4 * N], ki[4 * N];
bool ish[4 * N];
int n;

void minim(int, int, int, int, int, int);
void maxim(int, int, int, int, int, int);

void init() {
	for (int i = 0; i < N; i++) {
		ka[i] = 0;
		ki[i] = INF;
	}
}

void minim(int v, int l, int r, int tl, int tr, int h) {
	if (tr < l || r < tl) return;

	if (tl <= l && r <= tr) {
		ki[v] = min(ki[v], h);
		ka[v] = min(ka[v], ki[v]);
		ish[v] = 1;

		return;
	}

	int m = (l + r) / 2;
	if (ish[v]) {
		ish[v] = 0;
		ish[2 * v] = ish[2 * v + 1] = 1;

		maxim(2 * v, l, m, l, m, ka[v]);
		minim(2 * v, l, m, l, m, ki[v]);
		maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
		minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
		ka[v] = 0;
		ki[v] = INF;
	}
	minim(2 * v, l, m, tl, tr, h);
	minim(2 * v + 1, m + 1, r, tl, tr, h);
}

void maxim(int v, int l, int r, int tl, int tr, int h) {
	if (tr < l || r < tl) return;

	if (tl <= l && r <= tr) {
		ka[v] = max(ka[v], h);
		ki[v] = max(ki[v], ka[v]);
		ish[v] = 1;
		return;
	}
	int m = (l + r) / 2;
	if (ish[v]) {
		ish[v] = 0;

		ish[2 * v] = ish[2 * v + 1] = 1;
		minim(2 * v, l, m, l, m, ki[v]);
		maxim(2 * v, l, m, l, m, ka[v]);
		minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
		maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
		ka[v] = 0;
		ki[v] = INF;
	}
	maxim(2 * v, l, m, tl, tr, h);
	maxim(2 * v + 1, m + 1, r, tl, tr, h);
}

int get(int v, int l, int r, int x) {
	if (l == r) {
		return ka[v];
	}

	int m = (l + r) / 2;
	if (x <= m)
		return get(2 * v, l, m, x);
	else
		return get(2 * v + 1, m + 1, r, x);
}

void buildWall(int nn, int k, int op[], int left[], int right[], int height[],
			   int finalHeight[]) {
	n = nn;
	init();

	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			maxim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
		} else {
			minim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
		}
	}

	for (int i = 1; i <= n; i++) {
		minim(1, 1, n, i, i, INF);
		// maxim(1, 1, n, i, i, 0);
		finalHeight[i - 1] = get(1, 1, n, i);
	}

	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Correct 11 ms 16108 KB Output is correct
3 Correct 13 ms 15980 KB Output is correct
4 Correct 21 ms 16236 KB Output is correct
5 Correct 16 ms 16236 KB Output is correct
6 Correct 16 ms 16236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Correct 174 ms 23788 KB Output is correct
3 Correct 288 ms 19440 KB Output is correct
4 Correct 925 ms 24692 KB Output is correct
5 Correct 314 ms 25196 KB Output is correct
6 Correct 319 ms 25176 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Correct 12 ms 16108 KB Output is correct
3 Correct 14 ms 15980 KB Output is correct
4 Correct 26 ms 16236 KB Output is correct
5 Correct 16 ms 16236 KB Output is correct
6 Correct 17 ms 16236 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 184 ms 23788 KB Output is correct
9 Correct 279 ms 19436 KB Output is correct
10 Correct 842 ms 24700 KB Output is correct
11 Correct 307 ms 25196 KB Output is correct
12 Correct 297 ms 25212 KB Output is correct
13 Correct 11 ms 15980 KB Output is correct
14 Correct 166 ms 23788 KB Output is correct
15 Correct 56 ms 16748 KB Output is correct
16 Correct 849 ms 24940 KB Output is correct
17 Correct 303 ms 24940 KB Output is correct
18 Correct 301 ms 24920 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15980 KB Output is correct
2 Correct 12 ms 16108 KB Output is correct
3 Correct 12 ms 15980 KB Output is correct
4 Correct 20 ms 16196 KB Output is correct
5 Correct 17 ms 16256 KB Output is correct
6 Correct 17 ms 16236 KB Output is correct
7 Correct 13 ms 15980 KB Output is correct
8 Correct 166 ms 23916 KB Output is correct
9 Correct 281 ms 19436 KB Output is correct
10 Correct 853 ms 24664 KB Output is correct
11 Correct 322 ms 25196 KB Output is correct
12 Correct 300 ms 25192 KB Output is correct
13 Correct 11 ms 15980 KB Output is correct
14 Correct 165 ms 23788 KB Output is correct
15 Correct 55 ms 16748 KB Output is correct
16 Correct 832 ms 24940 KB Output is correct
17 Correct 300 ms 25004 KB Output is correct
18 Correct 302 ms 24972 KB Output is correct
19 Correct 1206 ms 63360 KB Output is correct
20 Correct 1202 ms 64632 KB Output is correct
21 Correct 1230 ms 67436 KB Output is correct
22 Correct 1204 ms 64624 KB Output is correct
23 Correct 1200 ms 64612 KB Output is correct
24 Correct 1209 ms 64684 KB Output is correct
25 Correct 1234 ms 64620 KB Output is correct
26 Correct 1199 ms 67180 KB Output is correct
27 Correct 1207 ms 67124 KB Output is correct
28 Correct 1216 ms 64492 KB Output is correct
29 Correct 1251 ms 64488 KB Output is correct
30 Correct 1212 ms 64508 KB Output is correct