# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
555900 |
2022-05-01T18:53:25 Z |
cheissmart |
Seats (IOI18_seats) |
C++14 |
|
2664 ms |
119224 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e6 + 7;
int H, W;
namespace DS {
pi t[N * 4];
int lz[N * 4];
void apply(int v, int x) {
lz[v] += x;
t[v].F += x;
}
void push(int v) {
apply(v * 2, lz[v]);
apply(v * 2 + 1, lz[v]);
lz[v] = 0;
}
pi add(pi a, pi b) {
if(a.F != b.F) return min(a, b);
a.S += b.S;
return a;
}
void build(int v = 1, int tl = 0, int tr = H * W) {
if(tr - tl == 1) {
t[v] = {0, 1};
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v] = add(t[v * 2], t[v * 2 + 1]);
}
void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = H * W) {
if(l <= tl && tr <= r) {
apply(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) upd(l, r, x, v * 2, tl, tm);
if(r > tm) upd(l, r, x, v * 2 + 1, tm, tr);
t[v] = add(t[v * 2], t[v * 2 + 1]);
}
}
V<vi> a;
vi R, C;
void upd(int i, int j, int op) {
int aux[] = {a[i][j], a[i + 1][j], a[i][j + 1], a[i + 1][j + 1]};
sort(aux, aux + 4);
if(aux[0] < aux[1]) DS::upd(aux[0], aux[1], op);//, cerr << aux[0] << " " << aux[1] << " " << op << endl;
if(aux[2] < aux[3]) DS::upd(aux[2], aux[3], op);//, cerr << aux[2] << " " << aux[3] << " " << op << endl;
}
void set_val(int i, int j, int x) {
upd(i - 1, j - 1, -1);
upd(i, j - 1, -1);
upd(i - 1, j, -1);
upd(i, j, -1);
a[i][j] = x;
upd(i - 1, j - 1, 1);
upd(i, j - 1, 1);
upd(i - 1, j, 1);
upd(i, j, 1);
}
void give_initial_chart(int _H, int _W, vi _R, vi _C) {
H = _H, W = _W, R = _R, C = _C;
a = V<vi> (H + 2, vi(W + 2, H * W));
for(int i = 0; i < SZ(R); i++) {
++R[i], ++C[i];
a[R[i]][C[i]] = i;
}
DS::build();
for(int i = 0; i <= H; i++)
for(int j = 0; j <= W; j++)
upd(i, j, 1);
}
int swap_seats(int x, int y) {
int val_x = a[R[x]][C[x]];
int val_y = a[R[y]][C[y]];
set_val(R[x], C[x], val_y);
set_val(R[y], C[y], val_x);
swap(R[x], R[y]), swap(C[x], C[y]);
return DS::t[1].S;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
15 ms |
444 KB |
Output is correct |
3 |
Correct |
23 ms |
452 KB |
Output is correct |
4 |
Correct |
13 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
476 KB |
Output is correct |
6 |
Correct |
20 ms |
428 KB |
Output is correct |
7 |
Correct |
22 ms |
424 KB |
Output is correct |
8 |
Correct |
19 ms |
468 KB |
Output is correct |
9 |
Correct |
21 ms |
452 KB |
Output is correct |
10 |
Correct |
22 ms |
444 KB |
Output is correct |
11 |
Correct |
19 ms |
448 KB |
Output is correct |
12 |
Correct |
13 ms |
444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
15 ms |
444 KB |
Output is correct |
3 |
Correct |
23 ms |
452 KB |
Output is correct |
4 |
Correct |
13 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
476 KB |
Output is correct |
6 |
Correct |
20 ms |
428 KB |
Output is correct |
7 |
Correct |
22 ms |
424 KB |
Output is correct |
8 |
Correct |
19 ms |
468 KB |
Output is correct |
9 |
Correct |
21 ms |
452 KB |
Output is correct |
10 |
Correct |
22 ms |
444 KB |
Output is correct |
11 |
Correct |
19 ms |
448 KB |
Output is correct |
12 |
Correct |
13 ms |
444 KB |
Output is correct |
13 |
Correct |
56 ms |
1184 KB |
Output is correct |
14 |
Correct |
82 ms |
1108 KB |
Output is correct |
15 |
Correct |
37 ms |
1296 KB |
Output is correct |
16 |
Correct |
27 ms |
1716 KB |
Output is correct |
17 |
Correct |
45 ms |
1236 KB |
Output is correct |
18 |
Correct |
44 ms |
1108 KB |
Output is correct |
19 |
Correct |
51 ms |
1216 KB |
Output is correct |
20 |
Correct |
51 ms |
1408 KB |
Output is correct |
21 |
Correct |
28 ms |
1296 KB |
Output is correct |
22 |
Correct |
30 ms |
1640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1709 ms |
68416 KB |
Output is correct |
2 |
Correct |
925 ms |
68384 KB |
Output is correct |
3 |
Correct |
925 ms |
68396 KB |
Output is correct |
4 |
Correct |
771 ms |
68288 KB |
Output is correct |
5 |
Correct |
838 ms |
68388 KB |
Output is correct |
6 |
Correct |
824 ms |
68292 KB |
Output is correct |
7 |
Correct |
825 ms |
68388 KB |
Output is correct |
8 |
Correct |
846 ms |
68380 KB |
Output is correct |
9 |
Correct |
891 ms |
68476 KB |
Output is correct |
10 |
Correct |
870 ms |
68396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
1108 KB |
Output is correct |
2 |
Correct |
130 ms |
7212 KB |
Output is correct |
3 |
Correct |
798 ms |
68332 KB |
Output is correct |
4 |
Correct |
1695 ms |
68404 KB |
Output is correct |
5 |
Correct |
733 ms |
76232 KB |
Output is correct |
6 |
Correct |
1852 ms |
119224 KB |
Output is correct |
7 |
Correct |
753 ms |
70968 KB |
Output is correct |
8 |
Correct |
905 ms |
68564 KB |
Output is correct |
9 |
Correct |
881 ms |
68828 KB |
Output is correct |
10 |
Correct |
866 ms |
72928 KB |
Output is correct |
11 |
Correct |
809 ms |
91740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
2016 KB |
Output is correct |
2 |
Correct |
80 ms |
1944 KB |
Output is correct |
3 |
Correct |
126 ms |
2144 KB |
Output is correct |
4 |
Correct |
164 ms |
2092 KB |
Output is correct |
5 |
Correct |
270 ms |
2768 KB |
Output is correct |
6 |
Correct |
1161 ms |
77184 KB |
Output is correct |
7 |
Correct |
1331 ms |
77120 KB |
Output is correct |
8 |
Correct |
1131 ms |
77284 KB |
Output is correct |
9 |
Correct |
2150 ms |
77132 KB |
Output is correct |
10 |
Correct |
1078 ms |
77124 KB |
Output is correct |
11 |
Correct |
1058 ms |
77160 KB |
Output is correct |
12 |
Correct |
1082 ms |
77124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
15 ms |
444 KB |
Output is correct |
3 |
Correct |
23 ms |
452 KB |
Output is correct |
4 |
Correct |
13 ms |
468 KB |
Output is correct |
5 |
Correct |
11 ms |
476 KB |
Output is correct |
6 |
Correct |
20 ms |
428 KB |
Output is correct |
7 |
Correct |
22 ms |
424 KB |
Output is correct |
8 |
Correct |
19 ms |
468 KB |
Output is correct |
9 |
Correct |
21 ms |
452 KB |
Output is correct |
10 |
Correct |
22 ms |
444 KB |
Output is correct |
11 |
Correct |
19 ms |
448 KB |
Output is correct |
12 |
Correct |
13 ms |
444 KB |
Output is correct |
13 |
Correct |
56 ms |
1184 KB |
Output is correct |
14 |
Correct |
82 ms |
1108 KB |
Output is correct |
15 |
Correct |
37 ms |
1296 KB |
Output is correct |
16 |
Correct |
27 ms |
1716 KB |
Output is correct |
17 |
Correct |
45 ms |
1236 KB |
Output is correct |
18 |
Correct |
44 ms |
1108 KB |
Output is correct |
19 |
Correct |
51 ms |
1216 KB |
Output is correct |
20 |
Correct |
51 ms |
1408 KB |
Output is correct |
21 |
Correct |
28 ms |
1296 KB |
Output is correct |
22 |
Correct |
30 ms |
1640 KB |
Output is correct |
23 |
Correct |
1709 ms |
68416 KB |
Output is correct |
24 |
Correct |
925 ms |
68384 KB |
Output is correct |
25 |
Correct |
925 ms |
68396 KB |
Output is correct |
26 |
Correct |
771 ms |
68288 KB |
Output is correct |
27 |
Correct |
838 ms |
68388 KB |
Output is correct |
28 |
Correct |
824 ms |
68292 KB |
Output is correct |
29 |
Correct |
825 ms |
68388 KB |
Output is correct |
30 |
Correct |
846 ms |
68380 KB |
Output is correct |
31 |
Correct |
891 ms |
68476 KB |
Output is correct |
32 |
Correct |
870 ms |
68396 KB |
Output is correct |
33 |
Correct |
55 ms |
1108 KB |
Output is correct |
34 |
Correct |
130 ms |
7212 KB |
Output is correct |
35 |
Correct |
798 ms |
68332 KB |
Output is correct |
36 |
Correct |
1695 ms |
68404 KB |
Output is correct |
37 |
Correct |
733 ms |
76232 KB |
Output is correct |
38 |
Correct |
1852 ms |
119224 KB |
Output is correct |
39 |
Correct |
753 ms |
70968 KB |
Output is correct |
40 |
Correct |
905 ms |
68564 KB |
Output is correct |
41 |
Correct |
881 ms |
68828 KB |
Output is correct |
42 |
Correct |
866 ms |
72928 KB |
Output is correct |
43 |
Correct |
809 ms |
91740 KB |
Output is correct |
44 |
Correct |
40 ms |
2016 KB |
Output is correct |
45 |
Correct |
80 ms |
1944 KB |
Output is correct |
46 |
Correct |
126 ms |
2144 KB |
Output is correct |
47 |
Correct |
164 ms |
2092 KB |
Output is correct |
48 |
Correct |
270 ms |
2768 KB |
Output is correct |
49 |
Correct |
1161 ms |
77184 KB |
Output is correct |
50 |
Correct |
1331 ms |
77120 KB |
Output is correct |
51 |
Correct |
1131 ms |
77284 KB |
Output is correct |
52 |
Correct |
2150 ms |
77132 KB |
Output is correct |
53 |
Correct |
1078 ms |
77124 KB |
Output is correct |
54 |
Correct |
1058 ms |
77160 KB |
Output is correct |
55 |
Correct |
1082 ms |
77124 KB |
Output is correct |
56 |
Correct |
99 ms |
1944 KB |
Output is correct |
57 |
Correct |
227 ms |
1936 KB |
Output is correct |
58 |
Correct |
444 ms |
2696 KB |
Output is correct |
59 |
Correct |
1442 ms |
69320 KB |
Output is correct |
60 |
Correct |
2664 ms |
69340 KB |
Output is correct |
61 |
Correct |
1524 ms |
69348 KB |
Output is correct |
62 |
Correct |
1249 ms |
73152 KB |
Output is correct |
63 |
Correct |
2582 ms |
71912 KB |
Output is correct |
64 |
Correct |
1608 ms |
70084 KB |
Output is correct |
65 |
Correct |
1392 ms |
69308 KB |
Output is correct |
66 |
Correct |
1622 ms |
69572 KB |
Output is correct |
67 |
Correct |
1611 ms |
74036 KB |
Output is correct |
68 |
Correct |
1292 ms |
83648 KB |
Output is correct |
69 |
Correct |
2572 ms |
92764 KB |
Output is correct |