oj.uz

Submission #160346

# Submission time Handle Problem Language Result Execution time Memory
160346 2019-10-27T03:48:11 Z tuna Wall (IOI14_wall) C++14
100 / 100
 1288 ms 78028 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define lc (id << 1)
#define mid ((l + r) >> 1)
#define rc ((id << 1) | 1)
using namespace std;

const int N = 1 << 21, inf = 1 << 17;

int tree[N], d[N << 1], u[N << 1];

void merge(int id, int c) {
	if (d[id] <= d[c]) {
		if (u[id] <= d[c]) {
			d[c] = u[c] = u[id];
		}
		if (d[c] < u[id] && u[id] <= u[c]) {
			u[c] = u[id];
		}
	}
	if (d[c] < d[id] && d[id] <= u[c]) {
		if (u[id] <= u[c]) {
			d[c] = d[id];
			u[c] = u[id];
		} else {
			d[c] = d[id];
		}
	}
	if (u[c] < d[id]) {
		d[c] = u[c] = d[id];
	}
}

void push(int id) {
	if (id >= N) {
		tree[id - N] = max(tree[id - N], d[id]);
		tree[id - N] = min(tree[id - N], u[id]);
	} else {
		merge(id, lc);
		merge(id, rc);
	}
	d[id] = 0;
	u[id] = inf;
}

void update(int id, int l, int r, int L, int R, int vd, int vu) {
	push(id);
	if (l > R || r < L) {
		return;
	}
	if (L <= l && r <= R) {
		d[id] = vd;
		u[id] = vu;
		return;
	}
	update(lc, l, mid, L, R, vd, vu);
	update(rc, mid + 1, r, L, R, vd, vu);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for (int i = 0; i < N << 1; i++) {
		u[i] = inf;
	}
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			update(1, 1, N, left[i] + 1, right[i] + 1, height[i], inf);
		} else {
			update(1, 1, N, left[i] + 1, right[i] + 1, 0, height[i]);
		}
	}
	for (int id = 1; id < N << 1; id++) {
		push(id);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = tree[i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 41336 KB Output is correct
2 Correct 85 ms 41464 KB Output is correct
3 Correct 83 ms 41336 KB Output is correct
4 Correct 90 ms 41592 KB Output is correct
5 Correct 87 ms 41592 KB Output is correct
6 Correct 170 ms 41592 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 41336 KB Output is correct
2 Correct 590 ms 55000 KB Output is correct
3 Correct 433 ms 48592 KB Output is correct
4 Correct 1126 ms 59520 KB Output is correct
5 Correct 597 ms 60408 KB Output is correct
6 Correct 615 ms 58972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 41364 KB Output is correct
2 Correct 88 ms 41464 KB Output is correct
3 Correct 83 ms 41400 KB Output is correct
4 Correct 91 ms 41720 KB Output is correct
5 Correct 90 ms 41592 KB Output is correct
6 Correct 89 ms 41720 KB Output is correct
7 Correct 82 ms 41464 KB Output is correct
8 Correct 598 ms 55096 KB Output is correct
9 Correct 432 ms 48568 KB Output is correct
10 Correct 1191 ms 59640 KB Output is correct
11 Correct 605 ms 60508 KB Output is correct
12 Correct 638 ms 59000 KB Output is correct
13 Correct 79 ms 41336 KB Output is correct
14 Correct 596 ms 55064 KB Output is correct
15 Correct 193 ms 42648 KB Output is correct
16 Correct 1153 ms 59792 KB Output is correct
17 Correct 610 ms 59128 KB Output is correct
18 Correct 611 ms 59128 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 41344 KB Output is correct
2 Correct 87 ms 41548 KB Output is correct
3 Correct 85 ms 41464 KB Output is correct
4 Correct 88 ms 41592 KB Output is correct
5 Correct 87 ms 41592 KB Output is correct
6 Correct 86 ms 41628 KB Output is correct
7 Correct 79 ms 41336 KB Output is correct
8 Correct 602 ms 55060 KB Output is correct
9 Correct 536 ms 48504 KB Output is correct
10 Correct 1119 ms 59412 KB Output is correct
11 Correct 596 ms 60496 KB Output is correct
12 Correct 598 ms 58932 KB Output is correct
13 Correct 79 ms 41308 KB Output is correct
14 Correct 620 ms 55084 KB Output is correct
15 Correct 142 ms 42616 KB Output is correct
16 Correct 1177 ms 59744 KB Output is correct
17 Correct 630 ms 59132 KB Output is correct
18 Correct 609 ms 59168 KB Output is correct
19 Correct 1288 ms 78028 KB Output is correct
20 Correct 1096 ms 75384 KB Output is correct
21 Correct 1112 ms 77944 KB Output is correct
22 Correct 1134 ms 75292 KB Output is correct
23 Correct 1094 ms 75256 KB Output is correct
24 Correct 1104 ms 75448 KB Output is correct
25 Correct 1101 ms 75440 KB Output is correct
26 Correct 1157 ms 77796 KB Output is correct
27 Correct 1120 ms 77756 KB Output is correct
28 Correct 1111 ms 75324 KB Output is correct
29 Correct 1113 ms 75384 KB Output is correct
30 Correct 1095 ms 75408 KB Output is correct