oj.uz

Submission #569075

# Submission time Handle Problem Language Result Execution time Memory
569075 2022-05-26T15:11:44 Z valerikk Seats (IOI18_seats) C++17
100 / 100
 3888 ms 141532 KB 
#include "seats.h"
#include <algorithm>

using namespace std;

struct SegTree {
	int n;
	vector<int> mn, cnt, delta;

	void apply(int v, int val) {
		mn[v] += val;
		delta[v] += val;
	}

	void push(int v) {
		apply(2 * v, delta[v]);
		apply(2 * v + 1, delta[v]);
		delta[v] = 0;
	}

	void pull(int v) {
		mn[v] = min(mn[2 * v], mn[2 * v + 1]);
		cnt[v] = (mn[2 * v] == mn[v] ? cnt[2 * v] : 0) + (mn[2 * v + 1] == mn[v] ? cnt[2 * v + 1] : 0);
	}

	void update(int v, int l, int r, int ql, int qr, int val) {
		if (l >= qr || r <= ql) 
			return;
		if (l >= ql && r <= qr) {
			apply(v, val);
			return;
		}
		
		push(v);
		
		int mid = (l + r) / 2;
		update(2 * v, l, mid, ql, qr, val);
		update(2 * v + 1, mid, r, ql, qr, val);

		pull(v);
	}

	void build(int v, int l, int r) {
		if (r - l == 1) {
			mn[v] = 0;
			cnt[v] = 1;
		} else {
			int mid = (l + r) / 2;
			build(2 * v, l, mid);
			build(2 * v + 1, mid, r);

			pull(v);
		}
	}

	int get(int need) {
		return mn[1] == need ? cnt[1] : 0;
	}

	SegTree() {}

	SegTree(int n) : n(n) {
		mn.resize(4 * n);
		cnt.resize(4 * n);
		delta.resize(4 * n);

		build(1, 0, n);
	}
};

const int N = 1e6 + 10;

int h, w, n;
int r[N], c[N];
vector<vector<int>> arr;
SegTree st;

void update(int x, int y, int delta) {
	vector<int> vals;
	for (int i = x; i <= x + 1; ++i) {
		for (int j = y; j <= y + 1; ++j) {
			vals.push_back(i >= 0 && i < h && j >= 0 && j < w ? arr[i][j] : n);
		}
	}
	sort(vals.begin(), vals.end());

	st.update(1, 0, n, vals[0], vals[1], delta);
	st.update(1, 0, n, vals[2], vals[3], delta);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h = H, w = W;
	
	n = h * w;

	arr.resize(h, vector<int>(w));
	for (int i = 0; i < h * w; ++i) {
		r[i] = R[i];
		c[i] = C[i];
		arr[r[i]][c[i]] = i;
	}

	st = {n};

	for (int x = -1; x < h; ++x) {
		for (int y = -1; y < w; ++y) {
			update(x, y, 1);
		}
	}
}

int swap_seats(int a, int b) {
	vector<pair<int, int>> changes;
	for (int i = r[a] - 1; i <= r[a]; ++i) {
		for (int j = c[a] - 1; j <= c[a]; ++j) {
			changes.push_back({i, j});
		}
	}
	for (int i = r[b] - 1; i <= r[b]; ++i) {
		for (int j = c[b] - 1; j <= c[b]; ++j) {
			changes.push_back({i, j});
		}
	}
	sort(changes.begin(), changes.end());
	changes.resize(unique(changes.begin(), changes.end()) - changes.begin());

	for (auto p : changes) {
		update(p.first, p.second, -1);
	}

	swap(arr[r[a]][c[a]], arr[r[b]][c[b]]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);

	for (auto p : changes) {
		update(p.first, p.second, 1);
	}

	return st.get(4);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Output is correct
2 Correct 28 ms 416 KB Output is correct
3 Correct 39 ms 420 KB Output is correct
4 Correct 34 ms 452 KB Output is correct
5 Correct 24 ms 416 KB Output is correct
6 Correct 37 ms 420 KB Output is correct
7 Correct 38 ms 460 KB Output is correct
8 Correct 37 ms 436 KB Output is correct
9 Correct 49 ms 408 KB Output is correct
10 Correct 40 ms 428 KB Output is correct
11 Correct 38 ms 424 KB Output is correct
12 Correct 28 ms 412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Output is correct
2 Correct 28 ms 416 KB Output is correct
3 Correct 39 ms 420 KB Output is correct
4 Correct 34 ms 452 KB Output is correct
5 Correct 24 ms 416 KB Output is correct
6 Correct 37 ms 420 KB Output is correct
7 Correct 38 ms 460 KB Output is correct
8 Correct 37 ms 436 KB Output is correct
9 Correct 49 ms 408 KB Output is correct
10 Correct 40 ms 428 KB Output is correct
11 Correct 38 ms 424 KB Output is correct
12 Correct 28 ms 412 KB Output is correct
13 Correct 86 ms 1272 KB Output is correct
14 Correct 105 ms 1356 KB Output is correct
15 Correct 71 ms 1316 KB Output is correct
16 Correct 51 ms 1748 KB Output is correct
17 Correct 78 ms 1292 KB Output is correct
18 Correct 75 ms 1268 KB Output is correct
19 Correct 68 ms 1308 KB Output is correct
20 Correct 70 ms 1500 KB Output is correct
21 Correct 54 ms 1236 KB Output is correct
22 Correct 52 ms 1784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2691 ms 90664 KB Output is correct
2 Correct 1388 ms 90688 KB Output is correct
3 Correct 1355 ms 90776 KB Output is correct
4 Correct 1150 ms 90668 KB Output is correct
5 Correct 1268 ms 90684 KB Output is correct
6 Correct 1159 ms 90688 KB Output is correct
7 Correct 1293 ms 90684 KB Output is correct
8 Correct 1364 ms 90688 KB Output is correct
9 Correct 1300 ms 90688 KB Output is correct
10 Correct 1279 ms 90796 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1276 KB Output is correct
2 Correct 191 ms 8352 KB Output is correct
3 Correct 1250 ms 90696 KB Output is correct
4 Correct 2498 ms 90688 KB Output is correct
5 Correct 1153 ms 90728 KB Output is correct
6 Correct 2369 ms 141532 KB Output is correct
7 Correct 1199 ms 90772 KB Output is correct
8 Correct 1381 ms 90696 KB Output is correct
9 Correct 1279 ms 91084 KB Output is correct
10 Correct 1256 ms 93780 KB Output is correct
11 Correct 1220 ms 114220 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2016 KB Output is correct
2 Correct 182 ms 1948 KB Output is correct
3 Correct 249 ms 1996 KB Output is correct
4 Correct 310 ms 2072 KB Output is correct
5 Correct 475 ms 2824 KB Output is correct
6 Correct 1767 ms 91664 KB Output is correct
7 Correct 2031 ms 91612 KB Output is correct
8 Correct 1761 ms 91660 KB Output is correct
9 Correct 3139 ms 91612 KB Output is correct
10 Correct 1700 ms 91612 KB Output is correct
11 Correct 1719 ms 91612 KB Output is correct
12 Correct 1659 ms 91608 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Output is correct
2 Correct 28 ms 416 KB Output is correct
3 Correct 39 ms 420 KB Output is correct
4 Correct 34 ms 452 KB Output is correct
5 Correct 24 ms 416 KB Output is correct
6 Correct 37 ms 420 KB Output is correct
7 Correct 38 ms 460 KB Output is correct
8 Correct 37 ms 436 KB Output is correct
9 Correct 49 ms 408 KB Output is correct
10 Correct 40 ms 428 KB Output is correct
11 Correct 38 ms 424 KB Output is correct
12 Correct 28 ms 412 KB Output is correct
13 Correct 86 ms 1272 KB Output is correct
14 Correct 105 ms 1356 KB Output is correct
15 Correct 71 ms 1316 KB Output is correct
16 Correct 51 ms 1748 KB Output is correct
17 Correct 78 ms 1292 KB Output is correct
18 Correct 75 ms 1268 KB Output is correct
19 Correct 68 ms 1308 KB Output is correct
20 Correct 70 ms 1500 KB Output is correct
21 Correct 54 ms 1236 KB Output is correct
22 Correct 52 ms 1784 KB Output is correct
23 Correct 2691 ms 90664 KB Output is correct
24 Correct 1388 ms 90688 KB Output is correct
25 Correct 1355 ms 90776 KB Output is correct
26 Correct 1150 ms 90668 KB Output is correct
27 Correct 1268 ms 90684 KB Output is correct
28 Correct 1159 ms 90688 KB Output is correct
29 Correct 1293 ms 90684 KB Output is correct
30 Correct 1364 ms 90688 KB Output is correct
31 Correct 1300 ms 90688 KB Output is correct
32 Correct 1279 ms 90796 KB Output is correct
33 Correct 92 ms 1276 KB Output is correct
34 Correct 191 ms 8352 KB Output is correct
35 Correct 1250 ms 90696 KB Output is correct
36 Correct 2498 ms 90688 KB Output is correct
37 Correct 1153 ms 90728 KB Output is correct
38 Correct 2369 ms 141532 KB Output is correct
39 Correct 1199 ms 90772 KB Output is correct
40 Correct 1381 ms 90696 KB Output is correct
41 Correct 1279 ms 91084 KB Output is correct
42 Correct 1256 ms 93780 KB Output is correct
43 Correct 1220 ms 114220 KB Output is correct
44 Correct 129 ms 2016 KB Output is correct
45 Correct 182 ms 1948 KB Output is correct
46 Correct 249 ms 1996 KB Output is correct
47 Correct 310 ms 2072 KB Output is correct
48 Correct 475 ms 2824 KB Output is correct
49 Correct 1767 ms 91664 KB Output is correct
50 Correct 2031 ms 91612 KB Output is correct
51 Correct 1761 ms 91660 KB Output is correct
52 Correct 3139 ms 91612 KB Output is correct
53 Correct 1700 ms 91612 KB Output is correct
54 Correct 1719 ms 91612 KB Output is correct
55 Correct 1659 ms 91608 KB Output is correct
56 Correct 196 ms 1960 KB Output is correct
57 Correct 408 ms 1932 KB Output is correct
58 Correct 668 ms 2872 KB Output is correct
59 Correct 2252 ms 91696 KB Output is correct
60 Correct 3888 ms 91680 KB Output is correct
61 Correct 2207 ms 91680 KB Output is correct
62 Correct 1804 ms 91648 KB Output is correct
63 Correct 3681 ms 91620 KB Output is correct
64 Correct 2361 ms 91672 KB Output is correct
65 Correct 2202 ms 91652 KB Output is correct
66 Correct 2363 ms 92000 KB Output is correct
67 Correct 2288 ms 94748 KB Output is correct
68 Correct 1928 ms 105956 KB Output is correct
69 Correct 3407 ms 115084 KB Output is correct