oj.uz

Submission #340285

# Submission time Handle Problem Language Result Execution time Memory
340285 2020-12-27T11:38:16 Z Kerim Wall (IOI14_wall) C++17
100 / 100
 1237 ms 73716 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 12 ms 16108 KB Output is correct
3 Correct 12 ms 16128 KB Output is correct
4 Correct 20 ms 16364 KB Output is correct
5 Correct 16 ms 16236 KB Output is correct
6 Correct 16 ms 16364 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 168 ms 29676 KB Output is correct
3 Correct 278 ms 23276 KB Output is correct
4 Correct 833 ms 34268 KB Output is correct
5 Correct 310 ms 35436 KB Output is correct
6 Correct 300 ms 33772 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 11 ms 16108 KB Output is correct
3 Correct 11 ms 16108 KB Output is correct
4 Correct 19 ms 16364 KB Output is correct
5 Correct 17 ms 16236 KB Output is correct
6 Correct 21 ms 16236 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 165 ms 29676 KB Output is correct
9 Correct 279 ms 23208 KB Output is correct
10 Correct 832 ms 34284 KB Output is correct
11 Correct 316 ms 35308 KB Output is correct
12 Correct 302 ms 33772 KB Output is correct
13 Correct 10 ms 15980 KB Output is correct
14 Correct 171 ms 29676 KB Output is correct
15 Correct 56 ms 17260 KB Output is correct
16 Correct 828 ms 34540 KB Output is correct
17 Correct 311 ms 34028 KB Output is correct
18 Correct 306 ms 34028 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15980 KB Output is correct
2 Correct 11 ms 16136 KB Output is correct
3 Correct 11 ms 16108 KB Output is correct
4 Correct 19 ms 16364 KB Output is correct
5 Correct 16 ms 16236 KB Output is correct
6 Correct 16 ms 16236 KB Output is correct
7 Correct 9 ms 15980 KB Output is correct
8 Correct 166 ms 29676 KB Output is correct
9 Correct 284 ms 23248 KB Output is correct
10 Correct 824 ms 34312 KB Output is correct
11 Correct 312 ms 35308 KB Output is correct
12 Correct 301 ms 33900 KB Output is correct
13 Correct 9 ms 15980 KB Output is correct
14 Correct 169 ms 29752 KB Output is correct
15 Correct 54 ms 17260 KB Output is correct
16 Correct 855 ms 34524 KB Output is correct
17 Correct 311 ms 34028 KB Output is correct
18 Correct 312 ms 34028 KB Output is correct
19 Correct 1228 ms 73708 KB Output is correct
20 Correct 1211 ms 71248 KB Output is correct
21 Correct 1222 ms 73708 KB Output is correct
22 Correct 1189 ms 71148 KB Output is correct
23 Correct 1194 ms 71148 KB Output is correct
24 Correct 1237 ms 71276 KB Output is correct
25 Correct 1236 ms 71148 KB Output is correct
26 Correct 1221 ms 73716 KB Output is correct
27 Correct 1223 ms 73708 KB Output is correct
28 Correct 1209 ms 71404 KB Output is correct
29 Correct 1218 ms 71276 KB Output is correct
30 Correct 1209 ms 71276 KB Output is correct