# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
235233 |
2020-05-27T13:10:28 Z |
lyc |
Seats (IOI18_seats) |
C++14 |
|
3890 ms |
173040 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
using ii=pair<int,int>;
vector<vector<int>> g;
vector<int> R, C;
int H, W;
int dx[] = {0,-1,0,1,0};
int dy[] = {-1,0,1,0,0};
struct node {
int s, e, mn, cnt, lazy;
node *l, *r;
node(int s, int e): s(s), e(e), mn(0), cnt(e-s+1), lazy(0) {
if (s != e) {
int m = (s+e)/2;
l = new node(s,m);
r = new node(m+1,e);
}
}
void prop() {
if (lazy == 0) return;
if (s != e) {
l->lazy += lazy;
r->lazy += lazy;
}
mn += lazy;
lazy = 0;
}
void update(int x, int y, int v) {
if (x > y) return;
prop();
int m = (s+e)/2;
if (s == x && e == y) { lazy += v; return; }
else if (y <= m) l->update(x,y,v);
else if (x > m) r->update(x,y,v);
else l->update(x,m,v), r->update(m+1,y,v);
l->prop(), r->prop();
mn = min(l->mn, r->mn);
cnt = 0;
if (l->mn == mn) cnt += l->cnt;
if (r->mn == mn) cnt += r->cnt;
}
} *root;
void add(int i, int j, int val) {
int v[4] = {0}, mn = H*W;
FOR(k,0,3){
int x = i+dx[k], y = j+dy[k];
if (x >= 0 and x < H && y >= 0 and y < W) v[k] = g[x][y];
else v[k] = H*W;
if (k < 2) mn = min(mn,v[k]);
}
sort(v,v+4);
int c = g[i][j];
//TRACE(c _ mn-1 _ "|" _ v[1] _ c-1 _ "|" _ val);
root->update(c,mn-1,val);
root->update(v[1],c-1,val);
}
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
H = _H, W = _W;
R = _R, C = _C;
FOR(i,0,H-1){ g.push_back(vector<int>(W)); }
FOR(i,0,SZ(R)-1){ g[R[i]][C[i]] = i; }
root = new node(0,H*W-1);
FOR(i,0,H-1){
FOR(j,0,W-1){
add(i,j,1);
}
}
//TRACE(root->mn _ root->cnt);
}
int swap_seats(int a, int b) {
vector<ii> pts;
//TRACE(R[a] _ C[a] _ R[b] _ C[b]);
FOR(i,0,4){
int x = R[a]+dx[i], y = C[a]+dy[i];
if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
}
FOR(i,0,4){
int x = R[b]+dx[i], y = C[b]+dy[i];
if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
}
sort(ALL(pts));
pts.resize(unique(ALL(pts))-pts.begin());
for (ii x : pts) {
add(x.first,x.second,-1);
}
swap(g[R[a]][C[a]],g[R[b]][C[b]]);
swap(R[a],R[b]);
swap(C[a],C[b]);
for (ii x : pts) {
add(x.first,x.second,1);
}
root->prop();
return (root->mn == 1 ? root->cnt : 0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
512 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
23 ms |
512 KB |
Output is correct |
5 |
Correct |
14 ms |
512 KB |
Output is correct |
6 |
Correct |
33 ms |
512 KB |
Output is correct |
7 |
Correct |
34 ms |
512 KB |
Output is correct |
8 |
Correct |
29 ms |
512 KB |
Output is correct |
9 |
Correct |
25 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
31 ms |
512 KB |
Output is correct |
12 |
Correct |
19 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
512 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
23 ms |
512 KB |
Output is correct |
5 |
Correct |
14 ms |
512 KB |
Output is correct |
6 |
Correct |
33 ms |
512 KB |
Output is correct |
7 |
Correct |
34 ms |
512 KB |
Output is correct |
8 |
Correct |
29 ms |
512 KB |
Output is correct |
9 |
Correct |
25 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
31 ms |
512 KB |
Output is correct |
12 |
Correct |
19 ms |
512 KB |
Output is correct |
13 |
Correct |
66 ms |
1792 KB |
Output is correct |
14 |
Correct |
88 ms |
1916 KB |
Output is correct |
15 |
Correct |
53 ms |
1824 KB |
Output is correct |
16 |
Correct |
23 ms |
2364 KB |
Output is correct |
17 |
Correct |
63 ms |
1912 KB |
Output is correct |
18 |
Correct |
47 ms |
1792 KB |
Output is correct |
19 |
Correct |
45 ms |
1916 KB |
Output is correct |
20 |
Correct |
42 ms |
2176 KB |
Output is correct |
21 |
Correct |
34 ms |
1792 KB |
Output is correct |
22 |
Correct |
35 ms |
2356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2487 ms |
122488 KB |
Output is correct |
2 |
Correct |
943 ms |
122616 KB |
Output is correct |
3 |
Correct |
1169 ms |
122616 KB |
Output is correct |
4 |
Correct |
647 ms |
122488 KB |
Output is correct |
5 |
Correct |
725 ms |
122616 KB |
Output is correct |
6 |
Correct |
938 ms |
122492 KB |
Output is correct |
7 |
Correct |
1020 ms |
122488 KB |
Output is correct |
8 |
Correct |
1061 ms |
122360 KB |
Output is correct |
9 |
Correct |
959 ms |
122488 KB |
Output is correct |
10 |
Correct |
789 ms |
122488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
1792 KB |
Output is correct |
2 |
Correct |
144 ms |
11956 KB |
Output is correct |
3 |
Correct |
815 ms |
122488 KB |
Output is correct |
4 |
Correct |
2491 ms |
122232 KB |
Output is correct |
5 |
Correct |
699 ms |
122108 KB |
Output is correct |
6 |
Correct |
2149 ms |
173040 KB |
Output is correct |
7 |
Correct |
719 ms |
122232 KB |
Output is correct |
8 |
Correct |
1189 ms |
122104 KB |
Output is correct |
9 |
Correct |
886 ms |
122292 KB |
Output is correct |
10 |
Correct |
796 ms |
125152 KB |
Output is correct |
11 |
Correct |
766 ms |
145484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
2036 KB |
Output is correct |
2 |
Correct |
104 ms |
2000 KB |
Output is correct |
3 |
Correct |
156 ms |
2140 KB |
Output is correct |
4 |
Correct |
179 ms |
2172 KB |
Output is correct |
5 |
Correct |
367 ms |
3348 KB |
Output is correct |
6 |
Correct |
1173 ms |
138744 KB |
Output is correct |
7 |
Correct |
1333 ms |
138872 KB |
Output is correct |
8 |
Correct |
1131 ms |
138744 KB |
Output is correct |
9 |
Correct |
2729 ms |
138672 KB |
Output is correct |
10 |
Correct |
981 ms |
138616 KB |
Output is correct |
11 |
Correct |
1002 ms |
138780 KB |
Output is correct |
12 |
Correct |
706 ms |
138616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
512 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
23 ms |
512 KB |
Output is correct |
5 |
Correct |
14 ms |
512 KB |
Output is correct |
6 |
Correct |
33 ms |
512 KB |
Output is correct |
7 |
Correct |
34 ms |
512 KB |
Output is correct |
8 |
Correct |
29 ms |
512 KB |
Output is correct |
9 |
Correct |
25 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
31 ms |
512 KB |
Output is correct |
12 |
Correct |
19 ms |
512 KB |
Output is correct |
13 |
Correct |
66 ms |
1792 KB |
Output is correct |
14 |
Correct |
88 ms |
1916 KB |
Output is correct |
15 |
Correct |
53 ms |
1824 KB |
Output is correct |
16 |
Correct |
23 ms |
2364 KB |
Output is correct |
17 |
Correct |
63 ms |
1912 KB |
Output is correct |
18 |
Correct |
47 ms |
1792 KB |
Output is correct |
19 |
Correct |
45 ms |
1916 KB |
Output is correct |
20 |
Correct |
42 ms |
2176 KB |
Output is correct |
21 |
Correct |
34 ms |
1792 KB |
Output is correct |
22 |
Correct |
35 ms |
2356 KB |
Output is correct |
23 |
Correct |
2487 ms |
122488 KB |
Output is correct |
24 |
Correct |
943 ms |
122616 KB |
Output is correct |
25 |
Correct |
1169 ms |
122616 KB |
Output is correct |
26 |
Correct |
647 ms |
122488 KB |
Output is correct |
27 |
Correct |
725 ms |
122616 KB |
Output is correct |
28 |
Correct |
938 ms |
122492 KB |
Output is correct |
29 |
Correct |
1020 ms |
122488 KB |
Output is correct |
30 |
Correct |
1061 ms |
122360 KB |
Output is correct |
31 |
Correct |
959 ms |
122488 KB |
Output is correct |
32 |
Correct |
789 ms |
122488 KB |
Output is correct |
33 |
Correct |
73 ms |
1792 KB |
Output is correct |
34 |
Correct |
144 ms |
11956 KB |
Output is correct |
35 |
Correct |
815 ms |
122488 KB |
Output is correct |
36 |
Correct |
2491 ms |
122232 KB |
Output is correct |
37 |
Correct |
699 ms |
122108 KB |
Output is correct |
38 |
Correct |
2149 ms |
173040 KB |
Output is correct |
39 |
Correct |
719 ms |
122232 KB |
Output is correct |
40 |
Correct |
1189 ms |
122104 KB |
Output is correct |
41 |
Correct |
886 ms |
122292 KB |
Output is correct |
42 |
Correct |
796 ms |
125152 KB |
Output is correct |
43 |
Correct |
766 ms |
145484 KB |
Output is correct |
44 |
Correct |
68 ms |
2036 KB |
Output is correct |
45 |
Correct |
104 ms |
2000 KB |
Output is correct |
46 |
Correct |
156 ms |
2140 KB |
Output is correct |
47 |
Correct |
179 ms |
2172 KB |
Output is correct |
48 |
Correct |
367 ms |
3348 KB |
Output is correct |
49 |
Correct |
1173 ms |
138744 KB |
Output is correct |
50 |
Correct |
1333 ms |
138872 KB |
Output is correct |
51 |
Correct |
1131 ms |
138744 KB |
Output is correct |
52 |
Correct |
2729 ms |
138672 KB |
Output is correct |
53 |
Correct |
981 ms |
138616 KB |
Output is correct |
54 |
Correct |
1002 ms |
138780 KB |
Output is correct |
55 |
Correct |
706 ms |
138616 KB |
Output is correct |
56 |
Correct |
138 ms |
2012 KB |
Output is correct |
57 |
Correct |
323 ms |
2160 KB |
Output is correct |
58 |
Correct |
379 ms |
3444 KB |
Output is correct |
59 |
Correct |
1939 ms |
138764 KB |
Output is correct |
60 |
Correct |
3890 ms |
138868 KB |
Output is correct |
61 |
Correct |
1274 ms |
138760 KB |
Output is correct |
62 |
Correct |
1160 ms |
139012 KB |
Output is correct |
63 |
Correct |
3570 ms |
138868 KB |
Output is correct |
64 |
Correct |
1759 ms |
138868 KB |
Output is correct |
65 |
Correct |
1757 ms |
138744 KB |
Output is correct |
66 |
Correct |
2060 ms |
139200 KB |
Output is correct |
67 |
Correct |
1620 ms |
141892 KB |
Output is correct |
68 |
Correct |
1104 ms |
153224 KB |
Output is correct |
69 |
Correct |
3714 ms |
162436 KB |
Output is correct |