oj.uz

Submission #83414

# Submission time Handle Problem Language Result Execution time Memory
83414 2018-11-07T13:47:35 Z Tusk Wall (IOI14_wall) C++14
61 / 100
 856 ms 263168 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 21;

int lo[N << 1], hi[N << 1];
int *ret, S;

void puttag(int p, int low, int high) {
	lo[p] = min(high, max(low, lo[p]));
	hi[p] = max(low, min(high, hi[p]));
}

void pushlz(int p, int l, int r) {
	if(l == r) ret[l] = min(hi[p], max(lo[p], ret[l]));
	else {
		puttag(p << 1, lo[p], hi[p]);
		puttag(p << 1 | 1, lo[p], hi[p]);
	}
	lo[p] = 0;
	hi[p] = INT_MAX;
}

void build(int p = 1, int l = 0, int r = S - 1) {
	hi[p] = INT_MAX;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void update(int x, int y, int low, int high, int p = 1, int l = 0, int r = S - 1) {
	if(x > r || l > y) return;
	if(x <= l && r <= y) return puttag(p, low, high);
	pushlz(p, l, r);
	int mid = (l + r) >> 1;
	update(x, y, low, high, p << 1, l, mid);
	update(x, y, low, high, p << 1 | 1, mid + 1, r);
}

void proc(int p = 1, int l = 0, int r = S - 1) {
	pushlz(p, l, r);
	if(l == r) return;
	int mid = (l + r) >> 1;
	proc(p << 1, l, mid);
	proc(p << 1 | 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	ret = finalHeight;
	S = n;
	build();
	for(int i = 0; i < k; i++) {
		if(op[i] == 1) update(left[i], right[i], height[i], INT_MAX);
		else if(op[i] == 2) update(left[i], right[i], 0, height[i]);
	}
	proc();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 560 KB Output is correct
3 Correct 4 ms 744 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 8 ms 1292 KB Output is correct
6 Correct 7 ms 1496 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1496 KB Output is correct
2 Correct 190 ms 14764 KB Output is correct
3 Correct 215 ms 14764 KB Output is correct
4 Correct 574 ms 30784 KB Output is correct
5 Correct 363 ms 41496 KB Output is correct
6 Correct 352 ms 50116 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 50116 KB Output is correct
2 Correct 4 ms 50116 KB Output is correct
3 Correct 3 ms 50116 KB Output is correct
4 Correct 8 ms 50116 KB Output is correct
5 Correct 8 ms 50116 KB Output is correct
6 Correct 8 ms 50116 KB Output is correct
7 Correct 2 ms 50116 KB Output is correct
8 Correct 185 ms 53220 KB Output is correct
9 Correct 204 ms 53220 KB Output is correct
10 Correct 606 ms 69192 KB Output is correct
11 Correct 385 ms 79908 KB Output is correct
12 Correct 360 ms 88516 KB Output is correct
13 Correct 2 ms 88516 KB Output is correct
14 Correct 193 ms 91252 KB Output is correct
15 Correct 48 ms 91252 KB Output is correct
16 Correct 584 ms 104380 KB Output is correct
17 Correct 365 ms 113416 KB Output is correct
18 Correct 380 ms 122448 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 122448 KB Output is correct
2 Correct 4 ms 122448 KB Output is correct
3 Correct 3 ms 122448 KB Output is correct
4 Correct 8 ms 122448 KB Output is correct
5 Correct 7 ms 122448 KB Output is correct
6 Correct 8 ms 122448 KB Output is correct
7 Correct 2 ms 122448 KB Output is correct
8 Correct 176 ms 125848 KB Output is correct
9 Correct 215 ms 125848 KB Output is correct
10 Correct 590 ms 141964 KB Output is correct
11 Correct 382 ms 152736 KB Output is correct
12 Correct 381 ms 161364 KB Output is correct
13 Correct 2 ms 161364 KB Output is correct
14 Correct 202 ms 163960 KB Output is correct
15 Correct 44 ms 163960 KB Output is correct
16 Correct 587 ms 177000 KB Output is correct
17 Correct 356 ms 186116 KB Output is correct
18 Correct 345 ms 195076 KB Output is correct
19 Correct 848 ms 253392 KB Output is correct
20 Correct 856 ms 257708 KB Output is correct
21 Runtime error 838 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
22 Halted 0 ms 0 KB -