oj.uz

Submission #532439

# Submission time Handle Problem Language Result Execution time Memory
532439 2022-03-02T21:48:20 Z sliviu Wall (IOI14_wall) C++17
100 / 100
 695 ms 107268 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int n, cur = 0;

struct node {
	int omin = 2000000000, omax = 0;
};

vector<node> t;
vector<int> sol;

void Propagate(int node, int left, int right) {
	t[2 * node].omin = max(t[node].omax, min(t[node].omin, t[2 * node].omin));
	t[2 * node].omax = min(t[node].omin, max(t[node].omax, t[2 * node].omax));
	t[2 * node + 1].omin = max(t[node].omax, min(t[node].omin, t[2 * node + 1].omin));
	t[2 * node + 1].omax = min(t[node].omin, max(t[node].omax, t[2 * node + 1].omax));
	t[node].omin = 2000000000, t[node].omax = 0;
}

void Update(int q, int h, int posleft, int posright, int node = 1, int left = 1, int right = n) {
	if (posleft <= left && right <= posright) {
		if (q == 1) {
			t[node].omax = max(t[node].omax, h);
			t[node].omin = max(t[node].omin, t[node].omax);
		}
		else {
			t[node].omin = min(t[node].omin, h);
			t[node].omax = min(t[node].omin, t[node].omax);
		}
		return;
	}
	Propagate(node, left, right);
	int m = (left + right) / 2;
	if (posleft <= m)
		Update(q, h, posleft, posright, 2 * node, left, m);
	if (posright > m)
		Update(q, h, posleft, posright, 2 * node + 1, m + 1, right);
}

void Solve(int node = 1, int left = 1, int right = n) {
	if (left == right) {
		sol.emplace_back(min(t[node].omin, t[node].omax));
		return;
	}
	Propagate(node, left, right);
	int m = (left + right) / 2;
	Solve(2 * node, left, m);
	Solve(2 * node + 1, m + 1, right);
}

void buildWall(int N, int k, int type[], int l[], int r[], int val[], int ans[]) {
	n = N;
	t = vector<node>(4 * n);
	for (int i = 0; i < k; ++i)
		Update(type[i], val[i], l[i] + 1, r[i] + 1);
	Solve();
	for (int i = 0; i < n; ++i)
		ans[i] = sol[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 147 ms 13876 KB Output is correct
3 Correct 151 ms 8212 KB Output is correct
4 Correct 418 ms 21880 KB Output is correct
5 Correct 259 ms 22972 KB Output is correct
6 Correct 251 ms 21540 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 412 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 940 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 147 ms 13996 KB Output is correct
9 Correct 149 ms 8208 KB Output is correct
10 Correct 408 ms 21968 KB Output is correct
11 Correct 255 ms 22972 KB Output is correct
12 Correct 247 ms 21436 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 137 ms 13892 KB Output is correct
15 Correct 28 ms 2136 KB Output is correct
16 Correct 392 ms 22208 KB Output is correct
17 Correct 250 ms 21564 KB Output is correct
18 Correct 240 ms 21536 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 5 ms 928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 132 ms 13892 KB Output is correct
9 Correct 149 ms 8216 KB Output is correct
10 Correct 399 ms 21920 KB Output is correct
11 Correct 281 ms 22972 KB Output is correct
12 Correct 248 ms 21420 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 142 ms 13844 KB Output is correct
15 Correct 24 ms 2196 KB Output is correct
16 Correct 408 ms 22252 KB Output is correct
17 Correct 250 ms 21556 KB Output is correct
18 Correct 254 ms 21564 KB Output is correct
19 Correct 646 ms 107260 KB Output is correct
20 Correct 635 ms 104812 KB Output is correct
21 Correct 623 ms 107268 KB Output is correct
22 Correct 695 ms 104700 KB Output is correct
23 Correct 691 ms 104788 KB Output is correct
24 Correct 653 ms 104656 KB Output is correct
25 Correct 685 ms 104668 KB Output is correct
26 Correct 660 ms 107268 KB Output is correct
27 Correct 622 ms 107208 KB Output is correct
28 Correct 606 ms 104856 KB Output is correct
29 Correct 627 ms 104732 KB Output is correct
30 Correct 622 ms 104824 KB Output is correct