oj.uz

Submission #98635

# Submission time Handle Problem Language Result Execution time Memory
98635 2019-02-25T02:13:59 Z PeppaPig Wall (IOI14_wall) C++14
100 / 100
 1202 ms 69496 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 2 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 12 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 201 ms 14096 KB Output is correct
3 Correct 218 ms 8140 KB Output is correct
4 Correct 575 ms 20548 KB Output is correct
5 Correct 322 ms 21528 KB Output is correct
6 Correct 400 ms 20056 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 8 ms 868 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 252 ms 14064 KB Output is correct
9 Correct 194 ms 8048 KB Output is correct
10 Correct 758 ms 20600 KB Output is correct
11 Correct 370 ms 21576 KB Output is correct
12 Correct 355 ms 19964 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 203 ms 14012 KB Output is correct
15 Correct 35 ms 2168 KB Output is correct
16 Correct 656 ms 20788 KB Output is correct
17 Correct 415 ms 20232 KB Output is correct
18 Correct 366 ms 20220 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 174 ms 13984 KB Output is correct
9 Correct 208 ms 8056 KB Output is correct
10 Correct 721 ms 20384 KB Output is correct
11 Correct 342 ms 21496 KB Output is correct
12 Correct 427 ms 19960 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 216 ms 14120 KB Output is correct
15 Correct 36 ms 2040 KB Output is correct
16 Correct 671 ms 20784 KB Output is correct
17 Correct 348 ms 20060 KB Output is correct
18 Correct 361 ms 20284 KB Output is correct
19 Correct 1202 ms 69368 KB Output is correct
20 Correct 897 ms 66924 KB Output is correct
21 Correct 808 ms 69496 KB Output is correct
22 Correct 991 ms 67008 KB Output is correct
23 Correct 912 ms 66864 KB Output is correct
24 Correct 787 ms 66872 KB Output is correct
25 Correct 866 ms 66852 KB Output is correct
26 Correct 850 ms 69372 KB Output is correct
27 Correct 822 ms 69308 KB Output is correct
28 Correct 896 ms 66904 KB Output is correct
29 Correct 912 ms 66912 KB Output is correct
30 Correct 1036 ms 66888 KB Output is correct