oj.uz

Submission #425941

# Submission time Handle Problem Language Result Execution time Memory
425941 2021-06-13T12:29:19 Z SuhaibSawalha1 Wall (IOI14_wall) C++17
100 / 100
 920 ms 69536 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6;
int seg[4 * N], seg2[4 * N], n;

void pull (int idx, int d, int u) {
	seg[idx] = min(seg[idx], d);
	seg[idx] = max(seg[idx], u);
	seg2[idx] = max(seg2[idx], u);
	seg2[idx] = min(seg2[idx], d);
}

void push_down (int idx) {
	pull(2 * idx, seg[idx], seg2[idx]);
	pull(2 * idx + 1, seg[idx], seg2[idx]);
	seg[idx] = 1e9;
	seg2[idx] = 0;
}

#define mid (L + R) / 2
void update (int st, int en, int h, int t, int idx = 1, int L = 0, int R = n - 1) {
	if (L > en || R < st) {
		return;
	}
	if (L >= st && R <= en) {
		pull(idx, t == 1 ? 1e9 : h, t == 1 ? h : 0);
		return;
	}
	push_down(idx);
	update(st, en, h, t, 2 * idx, L, mid);
	update(st, en, h, t, 2 * idx + 1, mid + 1, R);
}

void query (int idx, int L, int R, int f[]) {
	if (L == R) {
		f[L] = seg[idx];
		return;
	}
	push_down(idx);
	query(2 * idx, L, mid, f);
	query(2 * idx + 1, mid + 1, R, f);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	::n = n;
	for (int i = 0; i < k; ++i) {
		update(left[i], right[i], height[i], op[i]);
	}
	query(1, 0, n - 1, finalHeight);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 159 ms 8132 KB Output is correct
3 Correct 197 ms 4164 KB Output is correct
4 Correct 649 ms 10688 KB Output is correct
5 Correct 436 ms 11296 KB Output is correct
6 Correct 360 ms 11248 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 11 ms 768 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 230 ms 13932 KB Output is correct
9 Correct 207 ms 7928 KB Output is correct
10 Correct 715 ms 17768 KB Output is correct
11 Correct 394 ms 18000 KB Output is correct
12 Correct 443 ms 18284 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 197 ms 13900 KB Output is correct
15 Correct 41 ms 1916 KB Output is correct
16 Correct 669 ms 18064 KB Output is correct
17 Correct 377 ms 17964 KB Output is correct
18 Correct 364 ms 17980 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 8 ms 824 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 173 ms 14020 KB Output is correct
9 Correct 204 ms 7936 KB Output is correct
10 Correct 629 ms 17720 KB Output is correct
11 Correct 377 ms 17996 KB Output is correct
12 Correct 418 ms 18292 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 187 ms 13900 KB Output is correct
15 Correct 32 ms 1988 KB Output is correct
16 Correct 578 ms 18024 KB Output is correct
17 Correct 355 ms 17988 KB Output is correct
18 Correct 361 ms 18076 KB Output is correct
19 Correct 920 ms 65536 KB Output is correct
20 Correct 849 ms 66972 KB Output is correct
21 Correct 854 ms 69536 KB Output is correct
22 Correct 872 ms 67060 KB Output is correct
23 Correct 869 ms 66976 KB Output is correct
24 Correct 853 ms 66908 KB Output is correct
25 Correct 847 ms 66900 KB Output is correct
26 Correct 850 ms 69524 KB Output is correct
27 Correct 872 ms 69528 KB Output is correct
28 Correct 847 ms 66916 KB Output is correct
29 Correct 878 ms 67012 KB Output is correct
30 Correct 875 ms 67004 KB Output is correct