# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
802844 |
2023-08-02T15:04:36 Z |
IvanJ |
Seats (IOI18_seats) |
C++17 |
|
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();
}
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |