oj.uz

Submission #794327

# Submission time Handle Problem Language Result Execution time Memory
794327 2023-07-26T12:45:27 Z Sohsoh84 Seats (IOI18_seats) C++17
100 / 100
 2530 ms 110696 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define X		first
#define Y		second
#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int n, m, R[MAXN], C[MAXN], k;

namespace segment {
	pll sg[MAXN << 2];
	int lz[MAXN << 2];
	
	inline pll merge(pll a, pll b) {
		if (a.X == b.X) return {a.X, a.Y + b.Y};
		return min(a, b);
	}

	void build(int l = 0, int r = k - 1, int v = 1) {
		if (l == r) sg[v] = {0, 1};
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);
			sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	inline void push(int v) {
		sg[v].X += lz[v];
		if ((v << 1 | 1) < (MAXN << 2)) {
			lz[v << 1] += lz[v];
			lz[v << 1 | 1] += lz[v];
		}

		lz[v] = 0;
	}

	void update(int ql, int qr, int val, int l, int r, int v) {
		push(v);
		if (ql > r || qr < l) return;
		if (ql <= l && qr >= r) {
			lz[v] += val;
			push(v);
			return;
		}

		int mid = (l + r) >> 1;
		update(ql, qr, val, l, mid, v << 1);
		update(ql, qr, val, mid + 1, r, v << 1 | 1);
		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}

	void update(int l, int r, int val) {	
		if (r < l) return;
		r = min(r, k-1);
		update(l, r, val, 0, k-1, 1);
		
//		cerr << l << sep << r << endl;
	}
}

vector<vector<int>> A;

inline void add(int i, int j, int z) {
	vector<int> vec;
	for (int a = 0; a < 2; a++)
		for (int b = 0; b < 2; b++)
			vec.push_back({A[i + a][j + b]});

	sort(all(vec));
	segment::update(vec[0], vec[1] - 1, z);
	segment::update(vec[2], vec[3] - 1, z);
}

void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
	n = H_, m = W_;
	k = n * m;
	
	segment::build();

	A.resize(n + 5);
	for (int i = 0; i < n + 5; i++) {
		A[i].resize(m + 5, MAXN);
	}
	
	for (int i = 0; i < k; i++) {
		R[i] = R_[i] + 1;
		C[i] = C_[i] + 1;
		A[R[i]][C[i]] = i;
	}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			add(i, j, 1);
}

int swap_seats(int a, int b) {	
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			add(R[a] - i, C[a] - j, -1);

	A[R[a]][C[a]] = b;	

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			add(R[a] - i, C[a] - j, 1);


	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			add(R[b] - i, C[b] - j, -1);

	A[R[b]][C[b]] = a;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			add(R[b] - i, C[b] - j, 1);



	swap(R[a], R[b]);
	swap(C[a], C[b]);
	auto [_, cnt] = segment::sg[1];
	return cnt;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 400 KB Output is correct
2 Correct 20 ms 400 KB Output is correct
3 Correct 29 ms 408 KB Output is correct
4 Correct 20 ms 400 KB Output is correct
5 Correct 17 ms 412 KB Output is correct
6 Correct 25 ms 392 KB Output is correct
7 Correct 27 ms 408 KB Output is correct
8 Correct 25 ms 424 KB Output is correct
9 Correct 30 ms 408 KB Output is correct
10 Correct 27 ms 388 KB Output is correct
11 Correct 25 ms 392 KB Output is correct
12 Correct 18 ms 400 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 400 KB Output is correct
2 Correct 20 ms 400 KB Output is correct
3 Correct 29 ms 408 KB Output is correct
4 Correct 20 ms 400 KB Output is correct
5 Correct 17 ms 412 KB Output is correct
6 Correct 25 ms 392 KB Output is correct
7 Correct 27 ms 408 KB Output is correct
8 Correct 25 ms 424 KB Output is correct
9 Correct 30 ms 408 KB Output is correct
10 Correct 27 ms 388 KB Output is correct
11 Correct 25 ms 392 KB Output is correct
12 Correct 18 ms 400 KB Output is correct
13 Correct 74 ms 1164 KB Output is correct
14 Correct 66 ms 1144 KB Output is correct
15 Correct 42 ms 1352 KB Output is correct
16 Correct 34 ms 1676 KB Output is correct
17 Correct 50 ms 1244 KB Output is correct
18 Correct 48 ms 1148 KB Output is correct
19 Correct 50 ms 1196 KB Output is correct
20 Correct 42 ms 1368 KB Output is correct
21 Correct 33 ms 1356 KB Output is correct
22 Correct 45 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1556 ms 59772 KB Output is correct
2 Correct 912 ms 59856 KB Output is correct
3 Correct 892 ms 59888 KB Output is correct
4 Correct 828 ms 59840 KB Output is correct
5 Correct 879 ms 59948 KB Output is correct
6 Correct 773 ms 59836 KB Output is correct
7 Correct 825 ms 59836 KB Output is correct
8 Correct 851 ms 59888 KB Output is correct
9 Correct 938 ms 59776 KB Output is correct
10 Correct 828 ms 59852 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1148 KB Output is correct
2 Correct 123 ms 6940 KB Output is correct
3 Correct 855 ms 59820 KB Output is correct
4 Correct 1621 ms 59884 KB Output is correct
5 Correct 836 ms 79372 KB Output is correct
6 Correct 1671 ms 110696 KB Output is correct
7 Correct 809 ms 66344 KB Output is correct
8 Correct 908 ms 60012 KB Output is correct
9 Correct 809 ms 60340 KB Output is correct
10 Correct 862 ms 65964 KB Output is correct
11 Correct 945 ms 91112 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1280 KB Output is correct
2 Correct 127 ms 1292 KB Output is correct
3 Correct 179 ms 1276 KB Output is correct
4 Correct 226 ms 1568 KB Output is correct
5 Correct 321 ms 2216 KB Output is correct
6 Correct 1321 ms 79740 KB Output is correct
7 Correct 1429 ms 79744 KB Output is correct
8 Correct 1241 ms 79696 KB Output is correct
9 Correct 2296 ms 79748 KB Output is correct
10 Correct 1282 ms 79804 KB Output is correct
11 Correct 1275 ms 79692 KB Output is correct
12 Correct 1304 ms 79856 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 400 KB Output is correct
2 Correct 20 ms 400 KB Output is correct
3 Correct 29 ms 408 KB Output is correct
4 Correct 20 ms 400 KB Output is correct
5 Correct 17 ms 412 KB Output is correct
6 Correct 25 ms 392 KB Output is correct
7 Correct 27 ms 408 KB Output is correct
8 Correct 25 ms 424 KB Output is correct
9 Correct 30 ms 408 KB Output is correct
10 Correct 27 ms 388 KB Output is correct
11 Correct 25 ms 392 KB Output is correct
12 Correct 18 ms 400 KB Output is correct
13 Correct 74 ms 1164 KB Output is correct
14 Correct 66 ms 1144 KB Output is correct
15 Correct 42 ms 1352 KB Output is correct
16 Correct 34 ms 1676 KB Output is correct
17 Correct 50 ms 1244 KB Output is correct
18 Correct 48 ms 1148 KB Output is correct
19 Correct 50 ms 1196 KB Output is correct
20 Correct 42 ms 1368 KB Output is correct
21 Correct 33 ms 1356 KB Output is correct
22 Correct 45 ms 1664 KB Output is correct
23 Correct 1556 ms 59772 KB Output is correct
24 Correct 912 ms 59856 KB Output is correct
25 Correct 892 ms 59888 KB Output is correct
26 Correct 828 ms 59840 KB Output is correct
27 Correct 879 ms 59948 KB Output is correct
28 Correct 773 ms 59836 KB Output is correct
29 Correct 825 ms 59836 KB Output is correct
30 Correct 851 ms 59888 KB Output is correct
31 Correct 938 ms 59776 KB Output is correct
32 Correct 828 ms 59852 KB Output is correct
33 Correct 57 ms 1148 KB Output is correct
34 Correct 123 ms 6940 KB Output is correct
35 Correct 855 ms 59820 KB Output is correct
36 Correct 1621 ms 59884 KB Output is correct
37 Correct 836 ms 79372 KB Output is correct
38 Correct 1671 ms 110696 KB Output is correct
39 Correct 809 ms 66344 KB Output is correct
40 Correct 908 ms 60012 KB Output is correct
41 Correct 809 ms 60340 KB Output is correct
42 Correct 862 ms 65964 KB Output is correct
43 Correct 945 ms 91112 KB Output is correct
44 Correct 105 ms 1280 KB Output is correct
45 Correct 127 ms 1292 KB Output is correct
46 Correct 179 ms 1276 KB Output is correct
47 Correct 226 ms 1568 KB Output is correct
48 Correct 321 ms 2216 KB Output is correct
49 Correct 1321 ms 79740 KB Output is correct
50 Correct 1429 ms 79744 KB Output is correct
51 Correct 1241 ms 79696 KB Output is correct
52 Correct 2296 ms 79748 KB Output is correct
53 Correct 1282 ms 79804 KB Output is correct
54 Correct 1275 ms 79692 KB Output is correct
55 Correct 1304 ms 79856 KB Output is correct
56 Correct 163 ms 1300 KB Output is correct
57 Correct 279 ms 1352 KB Output is correct
58 Correct 454 ms 2064 KB Output is correct
59 Correct 1528 ms 60220 KB Output is correct
60 Correct 2530 ms 60236 KB Output is correct
61 Correct 1472 ms 60204 KB Output is correct
62 Correct 1295 ms 69848 KB Output is correct
63 Correct 2494 ms 66700 KB Output is correct
64 Correct 1708 ms 62128 KB Output is correct
65 Correct 1540 ms 60348 KB Output is correct
66 Correct 1594 ms 60636 KB Output is correct
67 Correct 1610 ms 66432 KB Output is correct
68 Correct 1351 ms 79640 KB Output is correct
69 Correct 2293 ms 91596 KB Output is correct