# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
394019 |
2021-04-25T08:32:44 Z |
phathnv |
Seats (IOI18_seats) |
C++11 |
|
3066 ms |
126632 KB |
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
struct Node{
int sum, minVal, cntMin;
Node(int x = 0, int cnt = 1){
sum = minVal = x;
cntMin = cnt;
}
Node operator + (const Node &oth){
Node res;
res.sum = sum + oth.sum;
res.minVal = min(minVal, sum + oth.minVal);
res.cntMin = cntMin * (minVal == res.minVal) + oth.cntMin * (sum + oth.minVal == res.minVal);
return res;
}
};
struct SegmentTree{
int n;
Node d[4000007];
void init(int _n){
n = _n;
}
void update(int id, int l, int r, int pos, int val){
if (pos < l || r < pos)
return;
if (l == r){
d[id].sum += val;
d[id].minVal += val;
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
d[id] = d[id << 1] + d[id << 1 | 1];
}
void update(int pos, int val){
update(1, 0, n - 1, pos, val);
}
int getCnt(){
return d[1].cntMin;
}
} st;
int h, w, tmp[4], nTmp;
vector<vector<int>> chair;
vector<int> x, y;
bool inSide(int x, int y){
return (0 <= x && x < h && 0 <= y && y < w);
}
void UpdateSquare(int x, int y, int type){
nTmp = 0;
for(int dx = 0; dx < 2; dx++)
for(int dy = 0; dy < 2; dy++)
if (inSide(x + dx, y + dy))
tmp[nTmp++] = chair[x + dx][y + dy];
sort(tmp, tmp + nTmp);
for(int i = 0; i < nTmp; i++){
st.update(tmp[i], type);
type = -type;
}
}
void give_initial_chart(int hh, int ww, vector<int> r, vector<int> c) {
h = hh;
w = ww;
x = r;
y = c;
chair.assign(h, vector<int>(w, 0));
for(int i = 0; i < w * h; i++)
chair[r[i]][c[i]] = i;
st.init(h * w);
for(int i = -1; i < h; i++)
for(int j = -1; j < w; j++)
UpdateSquare(i, j, 1);
}
int swap_seats(int a, int b) {
for(int dx = -1; dx < 1; dx++)
for(int dy = -1; dy < 1; dy++){
UpdateSquare(x[a] + dx, y[a] + dy, -1);
UpdateSquare(x[b] + dx, y[b] + dy, -1);
}
swap(chair[x[a]][y[a]], chair[x[b]][y[b]]);
swap(x[a], x[b]);
swap(y[a], y[b]);
for(int dx = -1; dx < 1; dx++)
for(int dy = -1; dy < 1; dy++){
UpdateSquare(x[a] + dx, y[a] + dy, +1);
UpdateSquare(x[b] + dx, y[b] + dy, +1);
}
return st.getCnt();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
47300 KB |
Output is correct |
2 |
Correct |
41 ms |
47348 KB |
Output is correct |
3 |
Correct |
52 ms |
47368 KB |
Output is correct |
4 |
Correct |
41 ms |
47384 KB |
Output is correct |
5 |
Correct |
38 ms |
47428 KB |
Output is correct |
6 |
Correct |
47 ms |
47416 KB |
Output is correct |
7 |
Correct |
49 ms |
47380 KB |
Output is correct |
8 |
Correct |
49 ms |
47412 KB |
Output is correct |
9 |
Correct |
48 ms |
47308 KB |
Output is correct |
10 |
Correct |
49 ms |
47308 KB |
Output is correct |
11 |
Correct |
48 ms |
47356 KB |
Output is correct |
12 |
Correct |
40 ms |
47296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
47300 KB |
Output is correct |
2 |
Correct |
41 ms |
47348 KB |
Output is correct |
3 |
Correct |
52 ms |
47368 KB |
Output is correct |
4 |
Correct |
41 ms |
47384 KB |
Output is correct |
5 |
Correct |
38 ms |
47428 KB |
Output is correct |
6 |
Correct |
47 ms |
47416 KB |
Output is correct |
7 |
Correct |
49 ms |
47380 KB |
Output is correct |
8 |
Correct |
49 ms |
47412 KB |
Output is correct |
9 |
Correct |
48 ms |
47308 KB |
Output is correct |
10 |
Correct |
49 ms |
47308 KB |
Output is correct |
11 |
Correct |
48 ms |
47356 KB |
Output is correct |
12 |
Correct |
40 ms |
47296 KB |
Output is correct |
13 |
Correct |
93 ms |
47728 KB |
Output is correct |
14 |
Correct |
101 ms |
47716 KB |
Output is correct |
15 |
Correct |
67 ms |
47720 KB |
Output is correct |
16 |
Correct |
61 ms |
48240 KB |
Output is correct |
17 |
Correct |
82 ms |
47820 KB |
Output is correct |
18 |
Correct |
88 ms |
47728 KB |
Output is correct |
19 |
Correct |
87 ms |
47760 KB |
Output is correct |
20 |
Correct |
74 ms |
47940 KB |
Output is correct |
21 |
Correct |
62 ms |
47760 KB |
Output is correct |
22 |
Correct |
62 ms |
48232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2019 ms |
74744 KB |
Output is correct |
2 |
Correct |
1484 ms |
75900 KB |
Output is correct |
3 |
Correct |
1537 ms |
75972 KB |
Output is correct |
4 |
Correct |
1351 ms |
75972 KB |
Output is correct |
5 |
Correct |
1399 ms |
75872 KB |
Output is correct |
6 |
Correct |
1334 ms |
75868 KB |
Output is correct |
7 |
Correct |
1440 ms |
75928 KB |
Output is correct |
8 |
Correct |
1524 ms |
75968 KB |
Output is correct |
9 |
Correct |
1429 ms |
75872 KB |
Output is correct |
10 |
Correct |
1457 ms |
75868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
47560 KB |
Output is correct |
2 |
Correct |
215 ms |
50672 KB |
Output is correct |
3 |
Correct |
1358 ms |
75952 KB |
Output is correct |
4 |
Correct |
2000 ms |
75864 KB |
Output is correct |
5 |
Correct |
1290 ms |
79820 KB |
Output is correct |
6 |
Correct |
1958 ms |
126632 KB |
Output is correct |
7 |
Correct |
1352 ms |
77116 KB |
Output is correct |
8 |
Correct |
1512 ms |
75796 KB |
Output is correct |
9 |
Correct |
1423 ms |
76160 KB |
Output is correct |
10 |
Correct |
1439 ms |
78896 KB |
Output is correct |
11 |
Correct |
1331 ms |
99240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
48308 KB |
Output is correct |
2 |
Correct |
114 ms |
48712 KB |
Output is correct |
3 |
Correct |
167 ms |
48796 KB |
Output is correct |
4 |
Correct |
241 ms |
48704 KB |
Output is correct |
5 |
Correct |
345 ms |
49148 KB |
Output is correct |
6 |
Correct |
1785 ms |
79944 KB |
Output is correct |
7 |
Correct |
1930 ms |
79916 KB |
Output is correct |
8 |
Correct |
1752 ms |
79944 KB |
Output is correct |
9 |
Correct |
2490 ms |
79944 KB |
Output is correct |
10 |
Correct |
1750 ms |
79804 KB |
Output is correct |
11 |
Correct |
1713 ms |
79812 KB |
Output is correct |
12 |
Correct |
1676 ms |
79784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
47300 KB |
Output is correct |
2 |
Correct |
41 ms |
47348 KB |
Output is correct |
3 |
Correct |
52 ms |
47368 KB |
Output is correct |
4 |
Correct |
41 ms |
47384 KB |
Output is correct |
5 |
Correct |
38 ms |
47428 KB |
Output is correct |
6 |
Correct |
47 ms |
47416 KB |
Output is correct |
7 |
Correct |
49 ms |
47380 KB |
Output is correct |
8 |
Correct |
49 ms |
47412 KB |
Output is correct |
9 |
Correct |
48 ms |
47308 KB |
Output is correct |
10 |
Correct |
49 ms |
47308 KB |
Output is correct |
11 |
Correct |
48 ms |
47356 KB |
Output is correct |
12 |
Correct |
40 ms |
47296 KB |
Output is correct |
13 |
Correct |
93 ms |
47728 KB |
Output is correct |
14 |
Correct |
101 ms |
47716 KB |
Output is correct |
15 |
Correct |
67 ms |
47720 KB |
Output is correct |
16 |
Correct |
61 ms |
48240 KB |
Output is correct |
17 |
Correct |
82 ms |
47820 KB |
Output is correct |
18 |
Correct |
88 ms |
47728 KB |
Output is correct |
19 |
Correct |
87 ms |
47760 KB |
Output is correct |
20 |
Correct |
74 ms |
47940 KB |
Output is correct |
21 |
Correct |
62 ms |
47760 KB |
Output is correct |
22 |
Correct |
62 ms |
48232 KB |
Output is correct |
23 |
Correct |
2019 ms |
74744 KB |
Output is correct |
24 |
Correct |
1484 ms |
75900 KB |
Output is correct |
25 |
Correct |
1537 ms |
75972 KB |
Output is correct |
26 |
Correct |
1351 ms |
75972 KB |
Output is correct |
27 |
Correct |
1399 ms |
75872 KB |
Output is correct |
28 |
Correct |
1334 ms |
75868 KB |
Output is correct |
29 |
Correct |
1440 ms |
75928 KB |
Output is correct |
30 |
Correct |
1524 ms |
75968 KB |
Output is correct |
31 |
Correct |
1429 ms |
75872 KB |
Output is correct |
32 |
Correct |
1457 ms |
75868 KB |
Output is correct |
33 |
Correct |
93 ms |
47560 KB |
Output is correct |
34 |
Correct |
215 ms |
50672 KB |
Output is correct |
35 |
Correct |
1358 ms |
75952 KB |
Output is correct |
36 |
Correct |
2000 ms |
75864 KB |
Output is correct |
37 |
Correct |
1290 ms |
79820 KB |
Output is correct |
38 |
Correct |
1958 ms |
126632 KB |
Output is correct |
39 |
Correct |
1352 ms |
77116 KB |
Output is correct |
40 |
Correct |
1512 ms |
75796 KB |
Output is correct |
41 |
Correct |
1423 ms |
76160 KB |
Output is correct |
42 |
Correct |
1439 ms |
78896 KB |
Output is correct |
43 |
Correct |
1331 ms |
99240 KB |
Output is correct |
44 |
Correct |
84 ms |
48308 KB |
Output is correct |
45 |
Correct |
114 ms |
48712 KB |
Output is correct |
46 |
Correct |
167 ms |
48796 KB |
Output is correct |
47 |
Correct |
241 ms |
48704 KB |
Output is correct |
48 |
Correct |
345 ms |
49148 KB |
Output is correct |
49 |
Correct |
1785 ms |
79944 KB |
Output is correct |
50 |
Correct |
1930 ms |
79916 KB |
Output is correct |
51 |
Correct |
1752 ms |
79944 KB |
Output is correct |
52 |
Correct |
2490 ms |
79944 KB |
Output is correct |
53 |
Correct |
1750 ms |
79804 KB |
Output is correct |
54 |
Correct |
1713 ms |
79812 KB |
Output is correct |
55 |
Correct |
1676 ms |
79784 KB |
Output is correct |
56 |
Correct |
133 ms |
48952 KB |
Output is correct |
57 |
Correct |
285 ms |
49092 KB |
Output is correct |
58 |
Correct |
579 ms |
49432 KB |
Output is correct |
59 |
Correct |
2309 ms |
75972 KB |
Output is correct |
60 |
Correct |
3066 ms |
75204 KB |
Output is correct |
61 |
Correct |
2282 ms |
91668 KB |
Output is correct |
62 |
Correct |
1877 ms |
93508 KB |
Output is correct |
63 |
Correct |
2882 ms |
92868 KB |
Output is correct |
64 |
Correct |
2362 ms |
91972 KB |
Output is correct |
65 |
Correct |
2318 ms |
91544 KB |
Output is correct |
66 |
Correct |
2384 ms |
91932 KB |
Output is correct |
67 |
Correct |
2342 ms |
94788 KB |
Output is correct |
68 |
Correct |
2024 ms |
105960 KB |
Output is correct |
69 |
Correct |
2810 ms |
115096 KB |
Output is correct |