oj.uz

Submission #48249

# Submission time Handle Problem Language Result Execution time Memory
48249 2018-05-11T04:52:13 Z cheater2k Wall (IOI14_wall) C++17
100 / 100
 1158 ms 262144 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

const int N = 2000005;

// SEGMENT TREE
int mn[N << 2];
int mx[N << 2];
int lz[N << 2];
int segpos[N];
#define mid ((l + r) >> 1)

void build(int v, int l, int r) {
	mn[v] = 0;
	mx[v] = 0;
	lz[v] = -1;
	if (l == r) {
		segpos[l] = v;
		return;
	}
	build(v << 1, l, mid);
	build(v << 1 | 1, mid + 1, r);
}

void push(int v, int l, int r) {
	if (lz[v] == -1) return;
	if (l < r) lz[v << 1] = lz[v], lz[v << 1 | 1] = lz[v];
	mn[v] = mx[v] = lz[v];
	lz[v] = -1;
}

void upd(int v, int l, int r, int L, int R, int val) {
	push(v, l, r);
	if (R < l || L > r) return;
	if (L <= l && r <= R) {
		lz[v] = val; push(v, l, r); return;
	}
	upd(v << 1, l, mid, L, R, val);
	upd(v << 1 | 1, mid + 1, r, L, R, val);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}

int find_smaller(int v, int l, int r, int leftmost, int h) {
	// find the smallest i >= leftmost s.t. a[i] < h
	push(v, l, r);
	if (r < leftmost) return N;
	if (l >= leftmost) {
		if (l == r) {
			if (mn[v] < h) return l;
			else return N;
		}
		if (mn[v] >= h) return N;
	}

	int gl = find_smaller(v << 1, l, mid, leftmost, h);
	if (gl != N) return gl;
	else return find_smaller(v << 1 | 1, mid + 1, r, leftmost, h);
}

int find_greater(int v, int l, int r, int leftmost, int h) {
	// find the smallest i >= leftmost s.t. a[i] > h
	push(v, l, r);
	if (r < leftmost) return N;
	if (l >= leftmost) {
		if (l == r) {
			if (mx[v] > h) return l;
			else return N;
		}
		if (mx[v] <= h) return N;
	}

	int gl = find_greater(v << 1, l, mid, leftmost, h);
	if (gl != N) return gl;
	else return find_greater(v << 1 | 1, mid + 1, r, leftmost, h);
}

void final(int v, int l, int r) {
	push(v, l, r);
	if (l == r) return;
	final(v << 1, l, mid);
	final(v << 1 | 1, mid + 1, r);
}

#undef mid

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(1, 0, n - 1);

	for (int i = 0; i < k; ++i) {
		if (op[i] == 1) { // add
			int pos = left[i];
			while(pos <= right[i]) {
				int posl = find_smaller(1, 0, n - 1, pos, height[i]);
				if (posl == N) break;
				int posr = find_greater(1, 0, n - 1, posl, height[i]);
				posr = min(posr - 1, right[i]);

				upd(1, 0, n - 1, posl, posr, height[i]);
				pos = posr + 1;
			}
		} else { // remove
			int pos = left[i];
			while(pos <= right[i]) {
				int posl = find_greater(1, 0, n - 1, pos, height[i]);
				if (posl == N) break;
				int posr = find_smaller(1, 0, n - 1, posl, height[i]);
				posr = min(posr - 1, right[i]);

				upd(1, 0, n - 1, posl, posr, height[i]);
				pos = posr + 1;
			}
		}
	}

	final(1, 0, n - 1);
	for (int i = 0; i < n; ++i) {
		finalHeight[i] = mn[segpos[i]];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 496 KB Output is correct
3 Correct 4 ms 644 KB Output is correct
4 Correct 11 ms 1336 KB Output is correct
5 Correct 9 ms 1336 KB Output is correct
6 Correct 9 ms 1460 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1460 KB Output is correct
2 Correct 175 ms 14800 KB Output is correct
3 Correct 148 ms 14992 KB Output is correct
4 Correct 426 ms 32232 KB Output is correct
5 Correct 466 ms 42880 KB Output is correct
6 Correct 435 ms 51440 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 51440 KB Output is correct
2 Correct 4 ms 51440 KB Output is correct
3 Correct 4 ms 51440 KB Output is correct
4 Correct 11 ms 51440 KB Output is correct
5 Correct 9 ms 51440 KB Output is correct
6 Correct 9 ms 51440 KB Output is correct
7 Correct 2 ms 51440 KB Output is correct
8 Correct 176 ms 53368 KB Output is correct
9 Correct 151 ms 53464 KB Output is correct
10 Correct 430 ms 70900 KB Output is correct
11 Correct 466 ms 81504 KB Output is correct
12 Correct 435 ms 90084 KB Output is correct
13 Correct 2 ms 90084 KB Output is correct
14 Correct 188 ms 91448 KB Output is correct
15 Correct 60 ms 91448 KB Output is correct
16 Correct 1094 ms 105892 KB Output is correct
17 Correct 523 ms 115048 KB Output is correct
18 Correct 522 ms 124052 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 124052 KB Output is correct
2 Correct 4 ms 124052 KB Output is correct
3 Correct 4 ms 124052 KB Output is correct
4 Correct 11 ms 124052 KB Output is correct
5 Correct 9 ms 124052 KB Output is correct
6 Correct 9 ms 124052 KB Output is correct
7 Correct 2 ms 124052 KB Output is correct
8 Correct 181 ms 126032 KB Output is correct
9 Correct 148 ms 126044 KB Output is correct
10 Correct 445 ms 143404 KB Output is correct
11 Correct 464 ms 154116 KB Output is correct
12 Correct 437 ms 162696 KB Output is correct
13 Correct 2 ms 162696 KB Output is correct
14 Correct 189 ms 164012 KB Output is correct
15 Correct 56 ms 164012 KB Output is correct
16 Correct 1142 ms 178572 KB Output is correct
17 Correct 541 ms 187668 KB Output is correct
18 Correct 561 ms 196616 KB Output is correct
19 Correct 1136 ms 262144 KB Output is correct
20 Correct 1099 ms 262144 KB Output is correct
21 Correct 1114 ms 262144 KB Output is correct
22 Correct 1112 ms 262144 KB Output is correct
23 Correct 1158 ms 262144 KB Output is correct
24 Correct 1091 ms 262144 KB Output is correct
25 Correct 1120 ms 262144 KB Output is correct
26 Correct 1098 ms 262144 KB Output is correct
27 Correct 1100 ms 262144 KB Output is correct
28 Correct 1106 ms 262144 KB Output is correct
29 Correct 1112 ms 262144 KB Output is correct
30 Correct 1084 ms 262144 KB Output is correct