oj.uz

Submission #820602

# Submission time Handle Problem Language Result Execution time Memory
820602 2023-08-11T04:59:52 Z pavement Seats (IOI18_seats) C++17
100 / 100
 1586 ms 180488 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair

using ii = pair<int, int>;

int H, W;
vector<int> R, C, delta;
vector<vector<int> > grid;

int cell(int r, int c, int v) {
	if (!(-1 <= r && r < H && -1 <= c && c < W)) return 0;
	int ret = 0;
	for (int dr : {0, 1}) {
		for (int dc : {0, 1}) {
			int nr = r + dr, nc = c + dc;
			if (0 <= nr && nr < H && 0 <= nc && nc < W && grid[nr][nc] <= v) {
				ret++;
			}
		}
	}
	return ret;
}

struct node {
	node *left, *right;
	int S, E, sum;
	ii val;
	void combine() {
		assert(S != E);
		auto right_val = right->val;
		right_val.first += left->sum;
		sum = left->sum + right->sum;
		if (left->val.first == right_val.first) {
			val = mp(left->val.first, left->val.second + right_val.second);
		} else {
			val = min(left->val, right_val);
		}
	}
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			sum = val.first = delta[S];
			val.second = 1;
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		combine();
	}
	void upd(int p) {
		if (S == E) {
			sum = val.first = delta[S];
			val.second = 1;
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) left->upd(p);
		else right->upd(p);
		combine();
	}
} *root;

void upd(int x) {
	delta[x] = 0;
	for (int dr : {-1, 0}) {
		for (int dc : {-1, 0}) {
			int nr = R[x] + dr, nc = C[x] + dc, tmp = cell(nr, nc, x - 1);
			if (tmp == 1 || tmp == 3) {
				delta[x]--;
			}
		}
	}
	for (int dr : {-1, 0}) {
		for (int dc : {-1, 0}) {
			int nr = R[x] + dr, nc = C[x] + dc, tmp = cell(nr, nc, x);
			if (tmp == 1 || tmp == 3) {
				delta[x]++;
			}
		}
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	::H = H;
	::W = W;
	::R = R;
	::C = C;
	delta.resize(H * W);
	::grid = vector<vector<int> >(H, vector<int>(W, 0));
	for (int i = 0; i < H * W; i++) {
		grid[R[i]][C[i]] = i;
	}
	for (int i = 0; i < H * W; i++) {
		upd(i);
	}
	root = new node(0, H * W - 1);
}

int swap_seats(int a, int b) {
	swap(grid[R[a]][C[a]], grid[R[b]][C[b]]);
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	for (auto [r, c] : {mp(R[a], C[a]), mp(R[b], C[b])}) {
		for (int dr = -1; dr <= 1; dr++) {
			for (int dc = -1; dc <= 1; dc++) {
				int nr = r + dr, nc = c + dc;
				if (0 <= nr && nr < H && 0 <= nc && nc < W) {
					upd(grid[nr][nc]);
					root->upd(grid[nr][nc]);
				}
			}
		}
	}
	return root->val.second;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 24 ms 428 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 19 ms 424 KB Output is correct
8 Correct 24 ms 428 KB Output is correct
9 Correct 20 ms 440 KB Output is correct
10 Correct 19 ms 432 KB Output is correct
11 Correct 16 ms 456 KB Output is correct
12 Correct 8 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 24 ms 428 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 19 ms 424 KB Output is correct
8 Correct 24 ms 428 KB Output is correct
9 Correct 20 ms 440 KB Output is correct
10 Correct 19 ms 432 KB Output is correct
11 Correct 16 ms 456 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 41 ms 1768 KB Output is correct
14 Correct 42 ms 1704 KB Output is correct
15 Correct 15 ms 1716 KB Output is correct
16 Correct 14 ms 2288 KB Output is correct
17 Correct 28 ms 1760 KB Output is correct
18 Correct 38 ms 1752 KB Output is correct
19 Correct 30 ms 1704 KB Output is correct
20 Correct 24 ms 2004 KB Output is correct
21 Correct 14 ms 1748 KB Output is correct
22 Correct 14 ms 2228 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 126372 KB Output is correct
2 Correct 418 ms 129348 KB Output is correct
3 Correct 390 ms 129284 KB Output is correct
4 Correct 405 ms 129616 KB Output is correct
5 Correct 397 ms 129848 KB Output is correct
6 Correct 385 ms 129612 KB Output is correct
7 Correct 384 ms 129660 KB Output is correct
8 Correct 404 ms 129640 KB Output is correct
9 Correct 389 ms 129484 KB Output is correct
10 Correct 385 ms 129696 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1792 KB Output is correct
2 Correct 71 ms 12888 KB Output is correct
3 Correct 399 ms 129340 KB Output is correct
4 Correct 524 ms 129336 KB Output is correct
5 Correct 358 ms 129208 KB Output is correct
6 Correct 717 ms 180488 KB Output is correct
7 Correct 432 ms 129552 KB Output is correct
8 Correct 413 ms 129640 KB Output is correct
9 Correct 416 ms 130032 KB Output is correct
10 Correct 443 ms 132768 KB Output is correct
11 Correct 407 ms 153024 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1636 KB Output is correct
2 Correct 59 ms 1832 KB Output is correct
3 Correct 73 ms 1780 KB Output is correct
4 Correct 101 ms 2052 KB Output is correct
5 Correct 118 ms 3336 KB Output is correct
6 Correct 558 ms 126868 KB Output is correct
7 Correct 582 ms 126828 KB Output is correct
8 Correct 571 ms 126872 KB Output is correct
9 Correct 703 ms 126732 KB Output is correct
10 Correct 519 ms 126708 KB Output is correct
11 Correct 525 ms 130068 KB Output is correct
12 Correct 494 ms 129936 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 24 ms 428 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 19 ms 424 KB Output is correct
8 Correct 24 ms 428 KB Output is correct
9 Correct 20 ms 440 KB Output is correct
10 Correct 19 ms 432 KB Output is correct
11 Correct 16 ms 456 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 41 ms 1768 KB Output is correct
14 Correct 42 ms 1704 KB Output is correct
15 Correct 15 ms 1716 KB Output is correct
16 Correct 14 ms 2288 KB Output is correct
17 Correct 28 ms 1760 KB Output is correct
18 Correct 38 ms 1752 KB Output is correct
19 Correct 30 ms 1704 KB Output is correct
20 Correct 24 ms 2004 KB Output is correct
21 Correct 14 ms 1748 KB Output is correct
22 Correct 14 ms 2228 KB Output is correct
23 Correct 580 ms 126372 KB Output is correct
24 Correct 418 ms 129348 KB Output is correct
25 Correct 390 ms 129284 KB Output is correct
26 Correct 405 ms 129616 KB Output is correct
27 Correct 397 ms 129848 KB Output is correct
28 Correct 385 ms 129612 KB Output is correct
29 Correct 384 ms 129660 KB Output is correct
30 Correct 404 ms 129640 KB Output is correct
31 Correct 389 ms 129484 KB Output is correct
32 Correct 385 ms 129696 KB Output is correct
33 Correct 37 ms 1792 KB Output is correct
34 Correct 71 ms 12888 KB Output is correct
35 Correct 399 ms 129340 KB Output is correct
36 Correct 524 ms 129336 KB Output is correct
37 Correct 358 ms 129208 KB Output is correct
38 Correct 717 ms 180488 KB Output is correct
39 Correct 432 ms 129552 KB Output is correct
40 Correct 413 ms 129640 KB Output is correct
41 Correct 416 ms 130032 KB Output is correct
42 Correct 443 ms 132768 KB Output is correct
43 Correct 407 ms 153024 KB Output is correct
44 Correct 55 ms 1636 KB Output is correct
45 Correct 59 ms 1832 KB Output is correct
46 Correct 73 ms 1780 KB Output is correct
47 Correct 101 ms 2052 KB Output is correct
48 Correct 118 ms 3336 KB Output is correct
49 Correct 558 ms 126868 KB Output is correct
50 Correct 582 ms 126828 KB Output is correct
51 Correct 571 ms 126872 KB Output is correct
52 Correct 703 ms 126732 KB Output is correct
53 Correct 519 ms 126708 KB Output is correct
54 Correct 525 ms 130068 KB Output is correct
55 Correct 494 ms 129936 KB Output is correct
56 Correct 123 ms 1992 KB Output is correct
57 Correct 231 ms 2012 KB Output is correct
58 Correct 310 ms 3320 KB Output is correct
59 Correct 1029 ms 131108 KB Output is correct
60 Correct 1586 ms 130936 KB Output is correct
61 Correct 853 ms 130904 KB Output is correct
62 Correct 624 ms 130900 KB Output is correct
63 Correct 1316 ms 130900 KB Output is correct
64 Correct 948 ms 130916 KB Output is correct
65 Correct 804 ms 130864 KB Output is correct
66 Correct 1057 ms 131324 KB Output is correct
67 Correct 919 ms 133952 KB Output is correct
68 Correct 714 ms 145280 KB Output is correct
69 Correct 1330 ms 154324 KB Output is correct