oj.uz

Submission #426364

# Submission time Handle Problem Language Result Execution time Memory
426364 2021-06-13T20:09:04 Z bipartite_matching Wall (IOI14_wall) C++14
100 / 100
 1162 ms 122804 KB 
#include <bits/stdc++.h>

#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;

vector<int> mintree(10000000, 0);
vector<int> maxtree(10000000, 0);

void updatemin(int node, int a, int b, int x, int y, int k) {
	if (a <= x && y <= b) {
		if (mintree[node] >= k) return;
		mintree[node] = k;
		if (maxtree[node] < mintree[node]) {
			maxtree[node] = k;
		}
		if (mintree[node * 2 + 1] < mintree[node]) {
			mintree[node * 2 + 1] = mintree[node];
			if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
				maxtree[node * 2 + 1] = mintree[node * 2 + 1];
			}
		}
		if (mintree[node * 2 + 2] < mintree[node]){
			mintree[node * 2 + 2] = mintree[node];
			if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
				maxtree[node * 2 + 2] = mintree[node * 2 + 2];
			}
		}
		return;
	}

	if (mintree[node * 2 + 1] < mintree[node]) {
		mintree[node * 2 + 1] = mintree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			maxtree[node * 2 + 1] = mintree[node * 2 + 1];
		}
	}
	if (mintree[node * 2 + 2] < mintree[node]){
		mintree[node * 2 + 2] = mintree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			maxtree[node * 2 + 2] = mintree[node * 2 + 2];
		}
	}
	if (maxtree[node * 2 + 1] > maxtree[node]) {
		maxtree[node * 2 + 1] = maxtree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			mintree[node * 2 + 1] = maxtree[node * 2 + 1];
		}
	}
	if (maxtree[node * 2 + 2] > maxtree[node]) {
		maxtree[node * 2 + 2] = maxtree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			mintree[node * 2 + 2] = maxtree[node * 2 + 2];
		}
	}
	if ((x + y) / 2 >= a) {
		updatemin(node * 2 + 1, a, b, x, (x + y) / 2, k);
	}
	if ((x + y) / 2 + 1 <= b) {
		updatemin(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
	}

	maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
	mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
	if (maxtree[node] < mintree[node]) {
		maxtree[node] = mintree[node];
	}
}

void updatemax(int node, int a, int b, int x, int y, int k) {
	if (a <= x && y <= b) {
		if (maxtree[node] <= k) return;
		maxtree[node] = k;
		if (maxtree[node] < mintree[node]) {
			mintree[node] = k;
		}
		if (maxtree[node * 2 + 1] > maxtree[node]) {
			maxtree[node * 2 + 1] = maxtree[node];
			if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
				mintree[node * 2 + 1] = maxtree[node * 2 + 1];
			}
		}
		if (maxtree[node * 2 + 2] > maxtree[node]) {
			maxtree[node * 2 + 2] = maxtree[node];
			if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
				mintree[node * 2 + 2] = maxtree[node * 2 + 2];
			}
		}
		return;
	}
	if (maxtree[node * 2 + 1] > maxtree[node]) {
		maxtree[node * 2 + 1] = maxtree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			mintree[node * 2 + 1] = maxtree[node * 2 + 1];
		}
	}
	if (maxtree[node * 2 + 2] > maxtree[node]) {
		maxtree[node * 2 + 2] = maxtree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			mintree[node * 2 + 2] = maxtree[node * 2 + 2];
		}
	}
	if (mintree[node * 2 + 1] < mintree[node]) {
		mintree[node * 2 + 1] = mintree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			maxtree[node * 2 + 1] = mintree[node * 2 + 1];
		}
	}
	if (mintree[node * 2 + 2] < mintree[node]){
		mintree[node * 2 + 2] = mintree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			maxtree[node * 2 + 2] = mintree[node * 2 + 2];
		}
	}

	if ((x + y) / 2 >= a) {
		updatemax(node * 2 + 1, a, b, x, (x + y) / 2, k);
	}
	if ((x + y) / 2 + 1 <= b) {
		updatemax(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
	}

	maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
	mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
	if (maxtree[node] < mintree[node]) {
		mintree[node] = maxtree[node];
	}
}

int pos = 0;
vector<int> heightfinal;

void search(int node, int x, int y, int target) {
	//cerr << target << " ---- " << mintree[node] << " ---- " << maxtree[node] << "  - - " << x << "--" << y << endl;
	if (mintree[node] == maxtree[node]) {
		for (int i = target; i <= y; i++) {
			heightfinal[i] = mintree[node];
		}
		pos = y + 1;
		return;
	}

	if (mintree[node * 2 + 1] < mintree[node]) {
		mintree[node * 2 + 1] = mintree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) maxtree[node * 2 + 1] = mintree[node * 2 + 1];
	}
	if (mintree[node * 2 + 2] < mintree[node]) {
		mintree[node * 2 + 2] = mintree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) maxtree[node * 2 + 2] = mintree[node * 2 + 2];
	}
	if (maxtree[node * 2 + 1] > maxtree[node]) {
		maxtree[node * 2 + 1] = maxtree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) mintree[node * 2 + 1] = maxtree[node * 2 + 1];
	}
	if (maxtree[node * 2 + 2] > maxtree[node]) {
		maxtree[node * 2 + 2] = maxtree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) mintree[node * 2 + 2] = maxtree[node * 2 + 2];
	}

	if ((x + y) / 2 >= target) {
		search(node * 2 + 1, x, (x + y) / 2, target);
	}
	else {
		search(node * 2 + 2, (x + y) / 2 + 1, y, target);
	}
	
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	forint(i, k) {
		if (op[i] == 1) {
			updatemin(0, left[i], right[i], 0, n - 1, height[i]);
		}
		else {
			updatemax(0, left[i], right[i], 0, n - 1, height[i]);
		}
	}
	
	forint(i, 12) {
		cerr << mintree[i] << " - " << maxtree[i] << endl;
	}

	heightfinal.resize(n);
	while (pos < n) {
		//cerr << "hello" << endl;
		search(0, 0, n - 1, pos);
	}

	forint(i, n) {
		finalHeight[i] = heightfinal[i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 78540 KB Output is correct
2 Correct 34 ms 78700 KB Output is correct
3 Correct 36 ms 78592 KB Output is correct
4 Correct 45 ms 78752 KB Output is correct
5 Correct 41 ms 78836 KB Output is correct
6 Correct 41 ms 78788 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 78540 KB Output is correct
2 Correct 195 ms 92148 KB Output is correct
3 Correct 220 ms 85788 KB Output is correct
4 Correct 585 ms 96968 KB Output is correct
5 Correct 441 ms 97944 KB Output is correct
6 Correct 381 ms 96432 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78476 KB Output is correct
2 Correct 38 ms 78668 KB Output is correct
3 Correct 38 ms 78552 KB Output is correct
4 Correct 44 ms 78780 KB Output is correct
5 Correct 42 ms 78840 KB Output is correct
6 Correct 43 ms 78844 KB Output is correct
7 Correct 35 ms 78532 KB Output is correct
8 Correct 207 ms 92200 KB Output is correct
9 Correct 226 ms 85788 KB Output is correct
10 Correct 560 ms 96904 KB Output is correct
11 Correct 425 ms 97964 KB Output is correct
12 Correct 415 ms 96504 KB Output is correct
13 Correct 42 ms 78548 KB Output is correct
14 Correct 202 ms 92192 KB Output is correct
15 Correct 70 ms 79756 KB Output is correct
16 Correct 788 ms 97164 KB Output is correct
17 Correct 403 ms 96616 KB Output is correct
18 Correct 409 ms 96592 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78532 KB Output is correct
2 Correct 37 ms 78584 KB Output is correct
3 Correct 38 ms 78544 KB Output is correct
4 Correct 44 ms 78840 KB Output is correct
5 Correct 47 ms 78756 KB Output is correct
6 Correct 45 ms 78872 KB Output is correct
7 Correct 34 ms 78496 KB Output is correct
8 Correct 200 ms 92096 KB Output is correct
9 Correct 224 ms 85764 KB Output is correct
10 Correct 583 ms 96964 KB Output is correct
11 Correct 384 ms 97964 KB Output is correct
12 Correct 383 ms 96500 KB Output is correct
13 Correct 43 ms 78508 KB Output is correct
14 Correct 244 ms 92268 KB Output is correct
15 Correct 75 ms 79840 KB Output is correct
16 Correct 758 ms 97284 KB Output is correct
17 Correct 407 ms 96588 KB Output is correct
18 Correct 402 ms 96584 KB Output is correct
19 Correct 1038 ms 122804 KB Output is correct
20 Correct 1032 ms 120164 KB Output is correct
21 Correct 1028 ms 122792 KB Output is correct
22 Correct 1128 ms 120328 KB Output is correct
23 Correct 1075 ms 120260 KB Output is correct
24 Correct 1075 ms 120264 KB Output is correct
25 Correct 1083 ms 120156 KB Output is correct
26 Correct 1080 ms 122692 KB Output is correct
27 Correct 1128 ms 122776 KB Output is correct
28 Correct 1072 ms 120264 KB Output is correct
29 Correct 1071 ms 120288 KB Output is correct
30 Correct 1162 ms 120268 KB Output is correct