# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
95278 |
2019-01-29T13:02:36 Z |
onjo0127 |
Seats (IOI18_seats) |
C++11 |
|
2162 ms |
145848 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
struct Node { int mn, mnc; };
struct Segtree {
vector<Node> tree;
vector<int> lazy;
void pull(int idx) {
Node lc = tree[idx*2], rc = tree[idx*2+1];
if(lc.mn < rc.mn) tree[idx] = lc;
if(lc.mn > rc.mn) tree[idx] = rc;
if(lc.mn == rc.mn) tree[idx] = {lc.mn, lc.mnc + rc.mnc};
}
void init(vector<int>& A, int idx, int s, int e) {
if(s == e) {
tree[idx] = {A[s], 1};
return;
}
int m = s+e >> 1;
init(A, idx*2, s, m);
init(A, idx*2+1, m+1, e);
pull(idx);
}
void upd_lazy(int idx, int s, int e) {
if(lazy[idx]) {
tree[idx].mn += lazy[idx];
if(s != e) {
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
}
lazy[idx] = 0;
}
}
void upd(int idx, int s, int e, int l, int r, int y) {
upd_lazy(idx, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r) {
lazy[idx] += y; upd_lazy(idx, s, e);
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, l, r, y);
upd(idx*2+1, m+1, e, l, r, y);
pull(idx);
}
};
const int dx[4] = {0, 0, 1, 1};
const int dy[4] = {0, 1, 0, 1};
int h, w;
Segtree seg;
vector<vector<int> > A;
vector<int> r, c;
pair<pii, pii> ch(int x, int y) {
vector<int> S;
for(int k=0; k<4; k++) S.push_back(A[x + dx[k]][y + dy[k]]);
sort(S.begin(), S.end());
return {{S[0], S[1] - 1}, {S[2], S[3] - 1}};
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
for(auto& it: R) ++it; for(auto& it: C) ++it;
r = R; c = C; h = H; w = W;
vector<int> P(H*W+2, 0);
for(int i=0; i<=H+1; i++) A.push_back(vector<int>(W+2, H*W+1));
for(int i=0; i<H*W; i++) A[R[i]][C[i]] = i+1;
for(int i=0; i<=H; i++) {
for(int j=0; j<=W; j++) {
pii p1, p2; tie(p1, p2) = ch(i, j);
++P[p1.fi]; --P[p1.se + 1];
++P[p2.fi]; --P[p2.se + 1];
}
}
for(int i=1, s=0; i<=H*W; i++) {
s += P[i], P[i] = s;
}
seg.tree.resize(4*H*W); seg.lazy.resize(4*H*W);
seg.init(P, 1, 1, H*W);
}
void update(int x, int y, int d) {
for(int k=0; k<4; k++) {
pii p1, p2; tie(p1, p2) = ch(x-dx[k], y-dy[k]);
seg.upd(1, 1, h*w, p1.fi, p1.se, d);
seg.upd(1, 1, h*w, p2.fi, p2.se, d);
}
}
int swap_seats(int a, int b) {
int ra = r[a], ca = c[a], rb = r[b], cb = c[b];
update(ra, ca, -1); update(rb, cb, -1);
swap(A[ra][ca], A[rb][cb]);
swap(r[a], r[b]); swap(c[a], c[b]);
update(ra, ca, +1); update(rb, cb, +1);
if(seg.tree[1].mn == 4) return seg.tree[1].mnc;
return 0;
}
Compilation message
seats.cpp: In member function 'void Segtree::init(std::vector<int>&, int, int, int)':
seats.cpp:23:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
seats.cpp: In member function 'void Segtree::upd(int, int, int, int, int, int)':
seats.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:68:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto& it: R) ++it; for(auto& it: C) ++it;
^~~
seats.cpp:68:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto& it: R) ++it; for(auto& it: C) ++it;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
504 KB |
Output is correct |
2 |
Correct |
30 ms |
504 KB |
Output is correct |
3 |
Correct |
43 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
25 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
504 KB |
Output is correct |
9 |
Correct |
35 ms |
504 KB |
Output is correct |
10 |
Correct |
40 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
504 KB |
Output is correct |
2 |
Correct |
30 ms |
504 KB |
Output is correct |
3 |
Correct |
43 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
25 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
504 KB |
Output is correct |
9 |
Correct |
35 ms |
504 KB |
Output is correct |
10 |
Correct |
40 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
13 |
Correct |
127 ms |
1400 KB |
Output is correct |
14 |
Correct |
94 ms |
1428 KB |
Output is correct |
15 |
Correct |
52 ms |
1464 KB |
Output is correct |
16 |
Correct |
42 ms |
1844 KB |
Output is correct |
17 |
Correct |
67 ms |
1404 KB |
Output is correct |
18 |
Correct |
59 ms |
1400 KB |
Output is correct |
19 |
Correct |
57 ms |
1396 KB |
Output is correct |
20 |
Correct |
52 ms |
1656 KB |
Output is correct |
21 |
Correct |
42 ms |
1400 KB |
Output is correct |
22 |
Correct |
46 ms |
1844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
734 ms |
94804 KB |
Output is correct |
2 |
Correct |
559 ms |
94968 KB |
Output is correct |
3 |
Correct |
515 ms |
95100 KB |
Output is correct |
4 |
Correct |
504 ms |
94856 KB |
Output is correct |
5 |
Correct |
506 ms |
94712 KB |
Output is correct |
6 |
Correct |
509 ms |
94840 KB |
Output is correct |
7 |
Correct |
511 ms |
94712 KB |
Output is correct |
8 |
Correct |
578 ms |
94840 KB |
Output is correct |
9 |
Correct |
571 ms |
94856 KB |
Output is correct |
10 |
Correct |
521 ms |
94712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
1400 KB |
Output is correct |
2 |
Correct |
130 ms |
8792 KB |
Output is correct |
3 |
Correct |
556 ms |
94728 KB |
Output is correct |
4 |
Correct |
782 ms |
94836 KB |
Output is correct |
5 |
Correct |
678 ms |
102516 KB |
Output is correct |
6 |
Correct |
1095 ms |
145848 KB |
Output is correct |
7 |
Correct |
568 ms |
97416 KB |
Output is correct |
8 |
Correct |
567 ms |
95096 KB |
Output is correct |
9 |
Correct |
559 ms |
95208 KB |
Output is correct |
10 |
Correct |
612 ms |
99624 KB |
Output is correct |
11 |
Correct |
736 ms |
118268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
2092 KB |
Output is correct |
2 |
Correct |
179 ms |
2068 KB |
Output is correct |
3 |
Correct |
246 ms |
2132 KB |
Output is correct |
4 |
Correct |
295 ms |
2468 KB |
Output is correct |
5 |
Correct |
460 ms |
3072 KB |
Output is correct |
6 |
Correct |
1161 ms |
103624 KB |
Output is correct |
7 |
Correct |
1215 ms |
103528 KB |
Output is correct |
8 |
Correct |
1190 ms |
103636 KB |
Output is correct |
9 |
Correct |
1569 ms |
103608 KB |
Output is correct |
10 |
Correct |
1072 ms |
103500 KB |
Output is correct |
11 |
Correct |
1136 ms |
103508 KB |
Output is correct |
12 |
Correct |
1114 ms |
103508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
504 KB |
Output is correct |
2 |
Correct |
30 ms |
504 KB |
Output is correct |
3 |
Correct |
43 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
25 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
504 KB |
Output is correct |
9 |
Correct |
35 ms |
504 KB |
Output is correct |
10 |
Correct |
40 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
13 |
Correct |
127 ms |
1400 KB |
Output is correct |
14 |
Correct |
94 ms |
1428 KB |
Output is correct |
15 |
Correct |
52 ms |
1464 KB |
Output is correct |
16 |
Correct |
42 ms |
1844 KB |
Output is correct |
17 |
Correct |
67 ms |
1404 KB |
Output is correct |
18 |
Correct |
59 ms |
1400 KB |
Output is correct |
19 |
Correct |
57 ms |
1396 KB |
Output is correct |
20 |
Correct |
52 ms |
1656 KB |
Output is correct |
21 |
Correct |
42 ms |
1400 KB |
Output is correct |
22 |
Correct |
46 ms |
1844 KB |
Output is correct |
23 |
Correct |
734 ms |
94804 KB |
Output is correct |
24 |
Correct |
559 ms |
94968 KB |
Output is correct |
25 |
Correct |
515 ms |
95100 KB |
Output is correct |
26 |
Correct |
504 ms |
94856 KB |
Output is correct |
27 |
Correct |
506 ms |
94712 KB |
Output is correct |
28 |
Correct |
509 ms |
94840 KB |
Output is correct |
29 |
Correct |
511 ms |
94712 KB |
Output is correct |
30 |
Correct |
578 ms |
94840 KB |
Output is correct |
31 |
Correct |
571 ms |
94856 KB |
Output is correct |
32 |
Correct |
521 ms |
94712 KB |
Output is correct |
33 |
Correct |
79 ms |
1400 KB |
Output is correct |
34 |
Correct |
130 ms |
8792 KB |
Output is correct |
35 |
Correct |
556 ms |
94728 KB |
Output is correct |
36 |
Correct |
782 ms |
94836 KB |
Output is correct |
37 |
Correct |
678 ms |
102516 KB |
Output is correct |
38 |
Correct |
1095 ms |
145848 KB |
Output is correct |
39 |
Correct |
568 ms |
97416 KB |
Output is correct |
40 |
Correct |
567 ms |
95096 KB |
Output is correct |
41 |
Correct |
559 ms |
95208 KB |
Output is correct |
42 |
Correct |
612 ms |
99624 KB |
Output is correct |
43 |
Correct |
736 ms |
118268 KB |
Output is correct |
44 |
Correct |
148 ms |
2092 KB |
Output is correct |
45 |
Correct |
179 ms |
2068 KB |
Output is correct |
46 |
Correct |
246 ms |
2132 KB |
Output is correct |
47 |
Correct |
295 ms |
2468 KB |
Output is correct |
48 |
Correct |
460 ms |
3072 KB |
Output is correct |
49 |
Correct |
1161 ms |
103624 KB |
Output is correct |
50 |
Correct |
1215 ms |
103528 KB |
Output is correct |
51 |
Correct |
1190 ms |
103636 KB |
Output is correct |
52 |
Correct |
1569 ms |
103608 KB |
Output is correct |
53 |
Correct |
1072 ms |
103500 KB |
Output is correct |
54 |
Correct |
1136 ms |
103508 KB |
Output is correct |
55 |
Correct |
1114 ms |
103508 KB |
Output is correct |
56 |
Correct |
201 ms |
2148 KB |
Output is correct |
57 |
Correct |
411 ms |
2036 KB |
Output is correct |
58 |
Correct |
594 ms |
3000 KB |
Output is correct |
59 |
Correct |
1511 ms |
95708 KB |
Output is correct |
60 |
Correct |
2162 ms |
95700 KB |
Output is correct |
61 |
Correct |
1287 ms |
95748 KB |
Output is correct |
62 |
Correct |
1256 ms |
99504 KB |
Output is correct |
63 |
Correct |
1970 ms |
98312 KB |
Output is correct |
64 |
Correct |
1559 ms |
96488 KB |
Output is correct |
65 |
Correct |
1292 ms |
95956 KB |
Output is correct |
66 |
Correct |
1534 ms |
96032 KB |
Output is correct |
67 |
Correct |
1506 ms |
100484 KB |
Output is correct |
68 |
Correct |
1252 ms |
109928 KB |
Output is correct |
69 |
Correct |
2050 ms |
119188 KB |
Output is correct |