oj.uz

답안 #802844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802844 2023-08-02T15:04:36 Z IvanJ 자리 배치 (IOI18_seats) C++17
100 / 100
 3155 ms 127032 KB 
#include "seats.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int n, m, pot = 1;
ii pos[maxn];
vector<vector<int>> mat;
int L[maxn * 4];
ii T[maxn * 4];

ii merge(ii A, ii B) {
	if(A.x < B.x) return A;
	if(A.x > B.x) return B;
	return {A.x, A.y + B.y};
}

void prop(int x) {
	if(L[x] == 0) return;
	T[x].x += L[x];
	if(x < pot) 
		L[x * 2] += L[x], L[x * 2 + 1] += L[x];
	L[x] = 0;
}

void add_range(int x, int lo, int hi, int a, int b, int v) {
	prop(x);
	if(hi < a || b < lo) return;
	if(a <= lo && hi <= b) {
		L[x] += v;
		prop(x);
		return;
	}
	int mid = (lo + hi) / 2;
	add_range(x * 2, lo, mid, a, b, v);
	add_range(x * 2 + 1, mid + 1, hi, a, b, v);
	T[x] = merge(T[x * 2], T[x * 2 + 1]);
}

int answer() {
	if(T[1].x > 4) exit(1);
	return T[1].y;
}

int check(int x, int y) {return (x >= 0) & (x < n) & (y >= 0) & (y < m);}

void update(int x, int y, int val) {
	vector<int> v;
	if(check(x, y)) v.pb(mat[x][y]);
	if(check(x, y + 1)) v.pb(mat[x][y + 1]);
	if(check(x + 1, y)) v.pb(mat[x + 1][y]);
	if(check(x + 1, y + 1)) v.pb(mat[x + 1][y + 1]);
	v.pb(n * m);
	sort(all(v));
	add_range(1, 0, pot - 1, v[0], v[1] - 1, 1 * val);
	if(v.size() >= 4) 
		add_range(1, 0, pot - 1, v[2], v[3] - 1, 3 * val);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H, m = W;
	while(pot < (n * m)) pot <<= 1;
	for(int i = 0;i < n * m;i++) T[i + pot].y = 1;
	for(int i = n * m;i < (pot << 1);i++) T[i + pot].x = 1e9;
	for(int i = pot - 1;i > 0;i--) T[i] = merge(T[i * 2], T[i * 2 + 1]);
	for(int i = 0;i < n;i++) 
		mat.pb(vector<int>(m, 0));
		
	for(int i = 0;i < n * m;i++) 
		mat[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
	
	for(int i = -1;i < n;i++) 
		for(int j = -1;j < m;j++) 
			update(i, j, 1);
}

int swap_seats(int a, int b) {
	set<ii> s;
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 2;j++) {
			s.insert({pos[a].x - i, pos[a].y - j});
			s.insert({pos[b].x - i, pos[b].y - j});
		}
	
	for(ii p : s) update(p.x, p.y, -1);
	swap(mat[pos[a].x][pos[a].y], mat[pos[b].x][pos[b].y]);
	swap(pos[a], pos[b]);
	for(ii p : s) update(p.x, p.y, +1);
	return answer();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 460 KB Output is correct
2 Correct 29 ms 444 KB Output is correct
3 Correct 40 ms 440 KB Output is correct
4 Correct 26 ms 456 KB Output is correct
5 Correct 23 ms 472 KB Output is correct
6 Correct 42 ms 440 KB Output is correct
7 Correct 40 ms 440 KB Output is correct
8 Correct 35 ms 464 KB Output is correct
9 Correct 37 ms 560 KB Output is correct
10 Correct 37 ms 456 KB Output is correct
11 Correct 35 ms 460 KB Output is correct
12 Correct 23 ms 464 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 460 KB Output is correct
2 Correct 29 ms 444 KB Output is correct
3 Correct 40 ms 440 KB Output is correct
4 Correct 26 ms 456 KB Output is correct
5 Correct 23 ms 472 KB Output is correct
6 Correct 42 ms 440 KB Output is correct
7 Correct 40 ms 440 KB Output is correct
8 Correct 35 ms 464 KB Output is correct
9 Correct 37 ms 560 KB Output is correct
10 Correct 37 ms 456 KB Output is correct
11 Correct 35 ms 460 KB Output is correct
12 Correct 23 ms 464 KB Output is correct
13 Correct 77 ms 1276 KB Output is correct
14 Correct 87 ms 1296 KB Output is correct
15 Correct 54 ms 1236 KB Output is correct
16 Correct 39 ms 1804 KB Output is correct
17 Correct 66 ms 1208 KB Output is correct
18 Correct 61 ms 1276 KB Output is correct
19 Correct 58 ms 1236 KB Output is correct
20 Correct 50 ms 1608 KB Output is correct
21 Correct 43 ms 1276 KB Output is correct
22 Correct 40 ms 1796 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1781 ms 76252 KB Output is correct
2 Correct 1038 ms 76216 KB Output is correct
3 Correct 1002 ms 76236 KB Output is correct
4 Correct 847 ms 76172 KB Output is correct
5 Correct 906 ms 76236 KB Output is correct
6 Correct 827 ms 76212 KB Output is correct
7 Correct 894 ms 76304 KB Output is correct
8 Correct 939 ms 76232 KB Output is correct
9 Correct 953 ms 76208 KB Output is correct
10 Correct 890 ms 76204 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 1292 KB Output is correct
2 Correct 154 ms 7920 KB Output is correct
3 Correct 866 ms 76144 KB Output is correct
4 Correct 1809 ms 76236 KB Output is correct
5 Correct 821 ms 76160 KB Output is correct
6 Correct 1838 ms 127032 KB Output is correct
7 Correct 859 ms 76236 KB Output is correct
8 Correct 1027 ms 76192 KB Output is correct
9 Correct 903 ms 76472 KB Output is correct
10 Correct 936 ms 79300 KB Output is correct
11 Correct 910 ms 98712 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 1996 KB Output is correct
2 Correct 166 ms 2024 KB Output is correct
3 Correct 222 ms 1960 KB Output is correct
4 Correct 276 ms 2016 KB Output is correct
5 Correct 448 ms 2820 KB Output is correct
6 Correct 1339 ms 77164 KB Output is correct
7 Correct 1541 ms 77148 KB Output is correct
8 Correct 1251 ms 77128 KB Output is correct
9 Correct 2431 ms 77152 KB Output is correct
10 Correct 1233 ms 77148 KB Output is correct
11 Correct 1265 ms 77188 KB Output is correct
12 Correct 1243 ms 77288 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 460 KB Output is correct
2 Correct 29 ms 444 KB Output is correct
3 Correct 40 ms 440 KB Output is correct
4 Correct 26 ms 456 KB Output is correct
5 Correct 23 ms 472 KB Output is correct
6 Correct 42 ms 440 KB Output is correct
7 Correct 40 ms 440 KB Output is correct
8 Correct 35 ms 464 KB Output is correct
9 Correct 37 ms 560 KB Output is correct
10 Correct 37 ms 456 KB Output is correct
11 Correct 35 ms 460 KB Output is correct
12 Correct 23 ms 464 KB Output is correct
13 Correct 77 ms 1276 KB Output is correct
14 Correct 87 ms 1296 KB Output is correct
15 Correct 54 ms 1236 KB Output is correct
16 Correct 39 ms 1804 KB Output is correct
17 Correct 66 ms 1208 KB Output is correct
18 Correct 61 ms 1276 KB Output is correct
19 Correct 58 ms 1236 KB Output is correct
20 Correct 50 ms 1608 KB Output is correct
21 Correct 43 ms 1276 KB Output is correct
22 Correct 40 ms 1796 KB Output is correct
23 Correct 1781 ms 76252 KB Output is correct
24 Correct 1038 ms 76216 KB Output is correct
25 Correct 1002 ms 76236 KB Output is correct
26 Correct 847 ms 76172 KB Output is correct
27 Correct 906 ms 76236 KB Output is correct
28 Correct 827 ms 76212 KB Output is correct
29 Correct 894 ms 76304 KB Output is correct
30 Correct 939 ms 76232 KB Output is correct
31 Correct 953 ms 76208 KB Output is correct
32 Correct 890 ms 76204 KB Output is correct
33 Correct 77 ms 1292 KB Output is correct
34 Correct 154 ms 7920 KB Output is correct
35 Correct 866 ms 76144 KB Output is correct
36 Correct 1809 ms 76236 KB Output is correct
37 Correct 821 ms 76160 KB Output is correct
38 Correct 1838 ms 127032 KB Output is correct
39 Correct 859 ms 76236 KB Output is correct
40 Correct 1027 ms 76192 KB Output is correct
41 Correct 903 ms 76472 KB Output is correct
42 Correct 936 ms 79300 KB Output is correct
43 Correct 910 ms 98712 KB Output is correct
44 Correct 106 ms 1996 KB Output is correct
45 Correct 166 ms 2024 KB Output is correct
46 Correct 222 ms 1960 KB Output is correct
47 Correct 276 ms 2016 KB Output is correct
48 Correct 448 ms 2820 KB Output is correct
49 Correct 1339 ms 77164 KB Output is correct
50 Correct 1541 ms 77148 KB Output is correct
51 Correct 1251 ms 77128 KB Output is correct
52 Correct 2431 ms 77152 KB Output is correct
53 Correct 1233 ms 77148 KB Output is correct
54 Correct 1265 ms 77188 KB Output is correct
55 Correct 1243 ms 77288 KB Output is correct
56 Correct 196 ms 1936 KB Output is correct
57 Correct 394 ms 1948 KB Output is correct
58 Correct 577 ms 2816 KB Output is correct
59 Correct 1772 ms 77148 KB Output is correct
60 Correct 3022 ms 77200 KB Output is correct
61 Correct 1559 ms 77316 KB Output is correct
62 Correct 1373 ms 77104 KB Output is correct
63 Correct 3155 ms 77156 KB Output is correct
64 Correct 2013 ms 77188 KB Output is correct
65 Correct 1637 ms 77164 KB Output is correct
66 Correct 1823 ms 77504 KB Output is correct
67 Correct 1967 ms 80176 KB Output is correct
68 Correct 1463 ms 91488 KB Output is correct
69 Correct 2666 ms 100652 KB Output is correct