oj.uz

Submission #1042369

# Submission time Handle Problem Language Result Execution time Memory
1042369 2024-08-03T02:54:47 Z pedroslrey Wall (IOI14_wall) C++14
100 / 100
 598 ms 84564 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 80 ms 13924 KB Output is correct
3 Correct 139 ms 9900 KB Output is correct
4 Correct 418 ms 21652 KB Output is correct
5 Correct 220 ms 22612 KB Output is correct
6 Correct 215 ms 21072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 71 ms 14044 KB Output is correct
9 Correct 139 ms 10068 KB Output is correct
10 Correct 381 ms 21504 KB Output is correct
11 Correct 216 ms 22704 KB Output is correct
12 Correct 218 ms 20976 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 71 ms 14092 KB Output is correct
15 Correct 24 ms 3932 KB Output is correct
16 Correct 468 ms 21844 KB Output is correct
17 Correct 220 ms 21192 KB Output is correct
18 Correct 223 ms 21184 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 75 ms 13924 KB Output is correct
9 Correct 135 ms 10016 KB Output is correct
10 Correct 390 ms 21608 KB Output is correct
11 Correct 225 ms 22668 KB Output is correct
12 Correct 212 ms 21072 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 72 ms 13880 KB Output is correct
15 Correct 25 ms 3932 KB Output is correct
16 Correct 461 ms 21944 KB Output is correct
17 Correct 229 ms 21332 KB Output is correct
18 Correct 232 ms 21408 KB Output is correct
19 Correct 553 ms 84304 KB Output is correct
20 Correct 585 ms 82004 KB Output is correct
21 Correct 562 ms 84480 KB Output is correct
22 Correct 528 ms 81824 KB Output is correct
23 Correct 539 ms 82000 KB Output is correct
24 Correct 545 ms 81860 KB Output is correct
25 Correct 545 ms 82004 KB Output is correct
26 Correct 565 ms 84532 KB Output is correct
27 Correct 552 ms 84564 KB Output is correct
28 Correct 557 ms 82000 KB Output is correct
29 Correct 598 ms 81972 KB Output is correct
30 Correct 598 ms 81892 KB Output is correct