# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
417668 |
2021-06-04T06:09:54 Z |
ja_kingy |
Seats (IOI18_seats) |
C++14 |
|
2973 ms |
118820 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> grid;
vector<int> r,c;
const int SZ = 1<<20;
struct LazyST {
int sz, mn[SZ*2], lz[SZ*2], cnt[SZ*2];
void build(vector<int>& vals, int l, int r, int t = 1) {
if (t == 1) sz = vals.size();
if (r - l == 1) {
mn[t] = vals[l];
cnt[t] = 1;
} else {
int m = l+r>>1;
build(vals, l, m, t*2);
build(vals, m, r, t*2+1);
pull(t);
}
}
void pull(int t) {
mn[t] = min(mn[t*2], mn[t*2+1]);
cnt[t] = 0;
if (mn[t*2] == mn[t]) cnt[t] += cnt[t*2];
if (mn[t*2+1] == mn[t]) cnt[t] += cnt[t*2+1];
}
void push(int t) {
mn[t*2] += lz[t];
mn[t*2+1] += lz[t];
lz[t*2] += lz[t];
lz[t*2+1] += lz[t];
lz[t] = 0;
}
void upd(int ul, int ur, int v, int t, int l, int r) {
if (ur <= l || r <= ul) return;
if (ul <= l && r <= ur) {
mn[t] += v;
lz[t] += v;
return;
}
push(t);
int m = l+r>>1;
upd(ul, ur, v, t*2, l, m);
upd(ul, ur, v, t*2+1, m, r);
pull(t);
}
void upd(int ul, int ur, int v) {upd(ul, ur, v, 1, 0, sz);}
} st;
void upd_sqr(int i, int j, int v) {
vector<int> pts;
for (int ni = 0; ni < 2; ++ni)
for (int nj = 0; nj < 2; ++nj)
pts.push_back(grid[i+ni][j+nj]);
sort(pts.begin(), pts.end());
st.upd(pts[0], pts[1], v);
st.upd(pts[2], pts[3], v);
}
void upd_pt(int i, int j, int v) {
for (auto& [di, dj] : (pair<int,int>[]){{0, 0}, {-1, 0}, {-1, -1}, {0, -1}}) {
upd_sqr(i+di, j+dj, v);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int i: R) r.push_back(i+1);
for (int i: C) c.push_back(i+1);
grid.assign(H+2, vector<int>(W+2, H*W));
for (int i = 0; i < H*W; ++i) {
grid[r[i]][c[i]] = i;
}
vector<int> d(H*W+1), vals(H*W);
for (int i = 0; i <= H; ++i) {
for (int j = 0; j <= W; ++j) {
vector<int> pts;
for (int ni = 0; ni < 2; ++ni)
for (int nj = 0; nj < 2; ++nj)
pts.push_back(grid[i+ni][j+nj]);
sort(pts.begin(), pts.end());
d[pts[0]]++;
d[pts[1]]--;
d[pts[2]]++;
d[pts[3]]--;
}
}
int v = 0;
for (int i = 0; i < H*W; ++i) {
v += d[i];
vals[i] = v;
}
st.build(vals, 0, H*W);
}
int swap_seats(int a, int b) {
upd_pt(r[a], c[a], -1);
upd_pt(r[b], c[b], -1);
swap(grid[r[a]][c[a]], grid[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
upd_pt(r[a], c[a], 1);
upd_pt(r[b], c[b], 1);
return st.cnt[1];
}
Compilation message
seats.cpp: In member function 'void LazyST::build(std::vector<int>&, int, int, int)':
seats.cpp:17:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | int m = l+r>>1;
| ~^~
seats.cpp: In member function 'void LazyST::upd(int, int, int, int, int, int)':
seats.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int m = l+r>>1;
| ~^~
seats.cpp: In function 'void upd_pt(int, int, int)':
seats.cpp:63:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for (auto& [di, dj] : (pair<int,int>[]){{0, 0}, {-1, 0}, {-1, -1}, {0, -1}}) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
432 KB |
Output is correct |
2 |
Correct |
33 ms |
436 KB |
Output is correct |
3 |
Correct |
49 ms |
424 KB |
Output is correct |
4 |
Correct |
33 ms |
436 KB |
Output is correct |
5 |
Correct |
38 ms |
452 KB |
Output is correct |
6 |
Correct |
42 ms |
444 KB |
Output is correct |
7 |
Correct |
49 ms |
424 KB |
Output is correct |
8 |
Correct |
41 ms |
424 KB |
Output is correct |
9 |
Correct |
44 ms |
412 KB |
Output is correct |
10 |
Correct |
51 ms |
424 KB |
Output is correct |
11 |
Correct |
42 ms |
460 KB |
Output is correct |
12 |
Correct |
30 ms |
440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
432 KB |
Output is correct |
2 |
Correct |
33 ms |
436 KB |
Output is correct |
3 |
Correct |
49 ms |
424 KB |
Output is correct |
4 |
Correct |
33 ms |
436 KB |
Output is correct |
5 |
Correct |
38 ms |
452 KB |
Output is correct |
6 |
Correct |
42 ms |
444 KB |
Output is correct |
7 |
Correct |
49 ms |
424 KB |
Output is correct |
8 |
Correct |
41 ms |
424 KB |
Output is correct |
9 |
Correct |
44 ms |
412 KB |
Output is correct |
10 |
Correct |
51 ms |
424 KB |
Output is correct |
11 |
Correct |
42 ms |
460 KB |
Output is correct |
12 |
Correct |
30 ms |
440 KB |
Output is correct |
13 |
Correct |
110 ms |
1284 KB |
Output is correct |
14 |
Correct |
119 ms |
1228 KB |
Output is correct |
15 |
Correct |
89 ms |
1364 KB |
Output is correct |
16 |
Correct |
75 ms |
1792 KB |
Output is correct |
17 |
Correct |
93 ms |
1332 KB |
Output is correct |
18 |
Correct |
88 ms |
1276 KB |
Output is correct |
19 |
Correct |
92 ms |
1304 KB |
Output is correct |
20 |
Correct |
81 ms |
1500 KB |
Output is correct |
21 |
Correct |
59 ms |
1376 KB |
Output is correct |
22 |
Correct |
64 ms |
1776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
921 ms |
67956 KB |
Output is correct |
2 |
Correct |
674 ms |
67988 KB |
Output is correct |
3 |
Correct |
695 ms |
67988 KB |
Output is correct |
4 |
Correct |
703 ms |
67996 KB |
Output is correct |
5 |
Correct |
786 ms |
68116 KB |
Output is correct |
6 |
Correct |
658 ms |
68000 KB |
Output is correct |
7 |
Correct |
685 ms |
67992 KB |
Output is correct |
8 |
Correct |
635 ms |
68008 KB |
Output is correct |
9 |
Correct |
623 ms |
67976 KB |
Output is correct |
10 |
Correct |
636 ms |
68104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
1292 KB |
Output is correct |
2 |
Correct |
182 ms |
6772 KB |
Output is correct |
3 |
Correct |
632 ms |
67988 KB |
Output is correct |
4 |
Correct |
829 ms |
68008 KB |
Output is correct |
5 |
Correct |
672 ms |
75828 KB |
Output is correct |
6 |
Correct |
1088 ms |
118820 KB |
Output is correct |
7 |
Correct |
668 ms |
71872 KB |
Output is correct |
8 |
Correct |
627 ms |
68004 KB |
Output is correct |
9 |
Correct |
621 ms |
68260 KB |
Output is correct |
10 |
Correct |
664 ms |
72648 KB |
Output is correct |
11 |
Correct |
669 ms |
91536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
1980 KB |
Output is correct |
2 |
Correct |
203 ms |
2012 KB |
Output is correct |
3 |
Correct |
321 ms |
1948 KB |
Output is correct |
4 |
Correct |
400 ms |
1996 KB |
Output is correct |
5 |
Correct |
685 ms |
2956 KB |
Output is correct |
6 |
Correct |
1579 ms |
76748 KB |
Output is correct |
7 |
Correct |
1562 ms |
76760 KB |
Output is correct |
8 |
Correct |
1538 ms |
76752 KB |
Output is correct |
9 |
Correct |
1871 ms |
76644 KB |
Output is correct |
10 |
Correct |
1416 ms |
76776 KB |
Output is correct |
11 |
Correct |
1405 ms |
76664 KB |
Output is correct |
12 |
Correct |
1383 ms |
76648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
432 KB |
Output is correct |
2 |
Correct |
33 ms |
436 KB |
Output is correct |
3 |
Correct |
49 ms |
424 KB |
Output is correct |
4 |
Correct |
33 ms |
436 KB |
Output is correct |
5 |
Correct |
38 ms |
452 KB |
Output is correct |
6 |
Correct |
42 ms |
444 KB |
Output is correct |
7 |
Correct |
49 ms |
424 KB |
Output is correct |
8 |
Correct |
41 ms |
424 KB |
Output is correct |
9 |
Correct |
44 ms |
412 KB |
Output is correct |
10 |
Correct |
51 ms |
424 KB |
Output is correct |
11 |
Correct |
42 ms |
460 KB |
Output is correct |
12 |
Correct |
30 ms |
440 KB |
Output is correct |
13 |
Correct |
110 ms |
1284 KB |
Output is correct |
14 |
Correct |
119 ms |
1228 KB |
Output is correct |
15 |
Correct |
89 ms |
1364 KB |
Output is correct |
16 |
Correct |
75 ms |
1792 KB |
Output is correct |
17 |
Correct |
93 ms |
1332 KB |
Output is correct |
18 |
Correct |
88 ms |
1276 KB |
Output is correct |
19 |
Correct |
92 ms |
1304 KB |
Output is correct |
20 |
Correct |
81 ms |
1500 KB |
Output is correct |
21 |
Correct |
59 ms |
1376 KB |
Output is correct |
22 |
Correct |
64 ms |
1776 KB |
Output is correct |
23 |
Correct |
921 ms |
67956 KB |
Output is correct |
24 |
Correct |
674 ms |
67988 KB |
Output is correct |
25 |
Correct |
695 ms |
67988 KB |
Output is correct |
26 |
Correct |
703 ms |
67996 KB |
Output is correct |
27 |
Correct |
786 ms |
68116 KB |
Output is correct |
28 |
Correct |
658 ms |
68000 KB |
Output is correct |
29 |
Correct |
685 ms |
67992 KB |
Output is correct |
30 |
Correct |
635 ms |
68008 KB |
Output is correct |
31 |
Correct |
623 ms |
67976 KB |
Output is correct |
32 |
Correct |
636 ms |
68104 KB |
Output is correct |
33 |
Correct |
120 ms |
1292 KB |
Output is correct |
34 |
Correct |
182 ms |
6772 KB |
Output is correct |
35 |
Correct |
632 ms |
67988 KB |
Output is correct |
36 |
Correct |
829 ms |
68008 KB |
Output is correct |
37 |
Correct |
672 ms |
75828 KB |
Output is correct |
38 |
Correct |
1088 ms |
118820 KB |
Output is correct |
39 |
Correct |
668 ms |
71872 KB |
Output is correct |
40 |
Correct |
627 ms |
68004 KB |
Output is correct |
41 |
Correct |
621 ms |
68260 KB |
Output is correct |
42 |
Correct |
664 ms |
72648 KB |
Output is correct |
43 |
Correct |
669 ms |
91536 KB |
Output is correct |
44 |
Correct |
164 ms |
1980 KB |
Output is correct |
45 |
Correct |
203 ms |
2012 KB |
Output is correct |
46 |
Correct |
321 ms |
1948 KB |
Output is correct |
47 |
Correct |
400 ms |
1996 KB |
Output is correct |
48 |
Correct |
685 ms |
2956 KB |
Output is correct |
49 |
Correct |
1579 ms |
76748 KB |
Output is correct |
50 |
Correct |
1562 ms |
76760 KB |
Output is correct |
51 |
Correct |
1538 ms |
76752 KB |
Output is correct |
52 |
Correct |
1871 ms |
76644 KB |
Output is correct |
53 |
Correct |
1416 ms |
76776 KB |
Output is correct |
54 |
Correct |
1405 ms |
76664 KB |
Output is correct |
55 |
Correct |
1383 ms |
76648 KB |
Output is correct |
56 |
Correct |
228 ms |
1904 KB |
Output is correct |
57 |
Correct |
483 ms |
1956 KB |
Output is correct |
58 |
Correct |
841 ms |
2896 KB |
Output is correct |
59 |
Correct |
2104 ms |
68908 KB |
Output is correct |
60 |
Correct |
2973 ms |
68920 KB |
Output is correct |
61 |
Correct |
1777 ms |
68960 KB |
Output is correct |
62 |
Correct |
1677 ms |
74676 KB |
Output is correct |
63 |
Correct |
2609 ms |
72724 KB |
Output is correct |
64 |
Correct |
2051 ms |
70208 KB |
Output is correct |
65 |
Correct |
1821 ms |
69004 KB |
Output is correct |
66 |
Correct |
2188 ms |
69224 KB |
Output is correct |
67 |
Correct |
2076 ms |
73612 KB |
Output is correct |
68 |
Correct |
1650 ms |
83352 KB |
Output is correct |
69 |
Correct |
2686 ms |
92396 KB |
Output is correct |