oj.uz

Submission #58062

# Submission time Handle Problem Language Result Execution time Memory
58062 2018-07-16T16:52:36 Z aome Wall (IOI14_wall) C++17
100 / 100
 1530 ms 226784 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 2000005;

struct Node {
	int min, max;

	Node() { min = 0, max = 1e9; }

	Node(int min, int max) : min(min), max(max) {}
};

struct SegmentTree {

	Node T[N << 2];

	#define mid ((l + r) >> 1)

	void upd(int i, int l, int r, int p, Node x) {
		if (l == r) {
			T[i] = x; return;
		}
		if (mid >= p) upd(i << 1, l, mid, p, x);
		else upd(i << 1 | 1, mid + 1, r, p, x);
		T[i].min = max(T[i << 1].min, T[i << 1 | 1].min);
		T[i].max = min(T[i << 1].max, T[i << 1 | 1].max);
	}

	int get1(int i, int l, int r, Node x) {
		if (l == r) return l;
		Node y;
		y.min = max(x.min, T[i << 1 | 1].min);
		y.max = min(x.max, T[i << 1 | 1].max);
		if (y.min > y.max) {
			return get1(i << 1 | 1, mid + 1, r, x);
		}
		return get1(i << 1, l, mid, y);
	}

	void get2(int i, int l, int r, int L, int R, Node& x) {
		if (l > R || L > r) return;
		if (L <= l && r <= R) {
			x.min = max(x.min, T[i].min);
			x.max = min(x.max, T[i].max);
			return;
		}
		get2(i << 1, l, mid, L, R, x);
		get2(i << 1 | 1, mid + 1, r, L, R, x);
	}

	#undef mid
} IT;

struct Event {
	int v, p, x, y, t;

	bool operator < (const Event& rhs) const {
		return v < rhs.v;
	}
};

void buildWall(int n, int m, int op[], int left[], int right[], int height[], int finalHeight[]) {
	vector<Event> events;
	for (int i = 0; i < m; ++i) {
		events.push_back({left[i], i, height[i], op[i], 0});
		events.push_back({right[i] + 1, i, height[i], op[i], 1});
	}
	sort(events.begin(), events.end());
	int ptr = 0;
	for (int i = 0; i < n; ++i) {
		// cout << "#at " << i << '\n';
		while (ptr < 2 * m && events[ptr].v <= i) {
			if (events[ptr].t == 0) {
				if (events[ptr].y == 2) {
					// cout << "#add2 " << events[ptr].p << '\n';
					IT.upd(1, 0, m - 1, events[ptr].p, Node(0, events[ptr].x));
				}
				else {
					// cout << "#add1 " << events[ptr].p << '\n';
					IT.upd(1, 0, m - 1, events[ptr].p, Node(events[ptr].x, 1e9));
				}
			}
			else {
				// cout << "#del " << events[ptr].p << '\n';
				IT.upd(1, 0, m - 1, events[ptr].p, Node());
			}
			++ptr;
		}
		int v, L, R;
		if (IT.T[1].min <= IT.T[1].max) {
			L = IT.T[1].min, R = IT.T[1].max, v = 0;
		}
		else {
			int p = IT.get1(1, 0, m - 1, Node());
			// cout << "#p " << p << '\n';
			v = height[p];
			Node x = Node();
			IT.get2(1, 0, m - 1, p + 1, m - 1, x);
			L = x.min, R = x.max;
		}
		// cout << v << ' ' << L << ' ' << R << '\n';
		if (v < L) finalHeight[i] = L;
		else if (v > R) finalHeight[i] = R;
		else finalHeight[i] = v;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 62968 KB Output is correct
2 Correct 68 ms 63808 KB Output is correct
3 Correct 56 ms 63808 KB Output is correct
4 Correct 59 ms 63808 KB Output is correct
5 Correct 60 ms 63920 KB Output is correct
6 Correct 62 ms 63948 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 63948 KB Output is correct
2 Correct 428 ms 92180 KB Output is correct
3 Correct 348 ms 92180 KB Output is correct
4 Correct 801 ms 94276 KB Output is correct
5 Correct 546 ms 94276 KB Output is correct
6 Correct 562 ms 94352 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94352 KB Output is correct
2 Correct 56 ms 94352 KB Output is correct
3 Correct 60 ms 94352 KB Output is correct
4 Correct 59 ms 94352 KB Output is correct
5 Correct 58 ms 94352 KB Output is correct
6 Correct 57 ms 94352 KB Output is correct
7 Correct 64 ms 94352 KB Output is correct
8 Correct 445 ms 94352 KB Output is correct
9 Correct 357 ms 94352 KB Output is correct
10 Correct 794 ms 94404 KB Output is correct
11 Correct 529 ms 94404 KB Output is correct
12 Correct 634 ms 94404 KB Output is correct
13 Correct 54 ms 94404 KB Output is correct
14 Correct 398 ms 94404 KB Output is correct
15 Correct 85 ms 94404 KB Output is correct
16 Correct 885 ms 94404 KB Output is correct
17 Correct 552 ms 94404 KB Output is correct
18 Correct 548 ms 94404 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94404 KB Output is correct
2 Correct 56 ms 94404 KB Output is correct
3 Correct 52 ms 94404 KB Output is correct
4 Correct 74 ms 94404 KB Output is correct
5 Correct 73 ms 94404 KB Output is correct
6 Correct 70 ms 94404 KB Output is correct
7 Correct 51 ms 94404 KB Output is correct
8 Correct 455 ms 94404 KB Output is correct
9 Correct 347 ms 94404 KB Output is correct
10 Correct 780 ms 94404 KB Output is correct
11 Correct 563 ms 94404 KB Output is correct
12 Correct 496 ms 94404 KB Output is correct
13 Correct 50 ms 94404 KB Output is correct
14 Correct 374 ms 94404 KB Output is correct
15 Correct 91 ms 94404 KB Output is correct
16 Correct 836 ms 94404 KB Output is correct
17 Correct 692 ms 94404 KB Output is correct
18 Correct 664 ms 94404 KB Output is correct
19 Correct 1262 ms 111808 KB Output is correct
20 Correct 1300 ms 122172 KB Output is correct
21 Correct 1194 ms 132600 KB Output is correct
22 Correct 1371 ms 143052 KB Output is correct
23 Correct 1250 ms 153496 KB Output is correct
24 Correct 1109 ms 164008 KB Output is correct
25 Correct 1300 ms 174440 KB Output is correct
26 Correct 1293 ms 184904 KB Output is correct
27 Correct 1197 ms 195380 KB Output is correct
28 Correct 1530 ms 205816 KB Output is correct
29 Correct 1204 ms 216336 KB Output is correct
30 Correct 1181 ms 226784 KB Output is correct