# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
745200 |
2023-05-19T14:36:58 Z |
danikoynov |
Seats (IOI18_seats) |
C++14 |
|
3257 ms |
134284 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
struct node
{
int mx, cnt;
node()
{
mx = 1e9;
cnt = 0;
}
};
node merge_node(node lf, node rf)
{
node nd;
nd.mx = min(lf.mx, rf.mx);
nd.cnt = 0;
if (lf.mx == nd.mx)
nd.cnt += lf.cnt;
if (rf.mx == nd.mx)
nd.cnt += rf.cnt;
return nd;
}
node tree[4 * maxn];
int lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root].mx += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void build(int root, int left, int right)
{
if (left == right)
{
tree[root].cnt = 1;
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
}
void update_range(int root, int left, int right, int qleft, int qright, int val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
int h, w, n;
vector < vector < int > > val;
void change(int x, int y, int k)
{
vector < int > cur;
cur.push_back(val[x][y]);
cur.push_back(val[x][y + 1]);
cur.push_back(val[x + 1][y]);
cur.push_back(val[x + 1][y + 1]);
///cout << "change " << x << " " << y << " " << k << endl;
sort(cur.begin(), cur.end());
update_range(1, 0, n - 1, cur[0], cur[1] - 1, k);
update_range(1, 0, n - 1, cur[2], cur[3] - 1, k);
//cout << cur[0] << " " << cur[1] - 1 << endl;
//cout << cur[2] << " " << cur[3] - 1 << endl;
}
void action_cell(int x, int y, int k)
{
for (int dx = -1; dx <= 0; dx ++)
for (int dy = -1; dy <= 0; dy ++)
{
change(x + dx, y + dy, k);
}
}
vector < int > r, c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
h = H;
w = W;
n = h * w;
build(1, 0, n - 1);
val.resize(h + 2, vector < int > (w + 2, n));
for (int i = 0; i < n; i ++)
{
val[R[i] + 1][C[i] + 1] = i;
r.push_back(R[i] + 1);
c.push_back(C[i] + 1);
}
for (int i = 0; i <= h; i ++)
for (int j = 0; j <= w; j ++)
change(i, j, 1);
//cout << tree[1].cnt << endl;
//exit(0);
}
int swap_seats(int a, int b)
{
action_cell(r[a], c[a], -1);
action_cell(r[b], c[b], -1);
swap(val[r[a]][c[a]], val[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
action_cell(r[a], c[a], +1);
action_cell(r[b], c[b], +1);
return tree[1].cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
31680 KB |
Output is correct |
2 |
Correct |
42 ms |
31732 KB |
Output is correct |
3 |
Correct |
50 ms |
31760 KB |
Output is correct |
4 |
Correct |
39 ms |
31712 KB |
Output is correct |
5 |
Correct |
36 ms |
31728 KB |
Output is correct |
6 |
Correct |
48 ms |
31692 KB |
Output is correct |
7 |
Correct |
52 ms |
31856 KB |
Output is correct |
8 |
Correct |
47 ms |
31732 KB |
Output is correct |
9 |
Correct |
46 ms |
31756 KB |
Output is correct |
10 |
Correct |
50 ms |
31828 KB |
Output is correct |
11 |
Correct |
47 ms |
31728 KB |
Output is correct |
12 |
Correct |
36 ms |
31732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
31680 KB |
Output is correct |
2 |
Correct |
42 ms |
31732 KB |
Output is correct |
3 |
Correct |
50 ms |
31760 KB |
Output is correct |
4 |
Correct |
39 ms |
31712 KB |
Output is correct |
5 |
Correct |
36 ms |
31728 KB |
Output is correct |
6 |
Correct |
48 ms |
31692 KB |
Output is correct |
7 |
Correct |
52 ms |
31856 KB |
Output is correct |
8 |
Correct |
47 ms |
31732 KB |
Output is correct |
9 |
Correct |
46 ms |
31756 KB |
Output is correct |
10 |
Correct |
50 ms |
31828 KB |
Output is correct |
11 |
Correct |
47 ms |
31728 KB |
Output is correct |
12 |
Correct |
36 ms |
31732 KB |
Output is correct |
13 |
Correct |
91 ms |
32276 KB |
Output is correct |
14 |
Correct |
106 ms |
32340 KB |
Output is correct |
15 |
Correct |
71 ms |
32424 KB |
Output is correct |
16 |
Correct |
62 ms |
32832 KB |
Output is correct |
17 |
Correct |
82 ms |
32356 KB |
Output is correct |
18 |
Correct |
77 ms |
32328 KB |
Output is correct |
19 |
Correct |
76 ms |
32360 KB |
Output is correct |
20 |
Correct |
76 ms |
32460 KB |
Output is correct |
21 |
Correct |
66 ms |
32500 KB |
Output is correct |
22 |
Correct |
57 ms |
32832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2057 ms |
67488 KB |
Output is correct |
2 |
Correct |
1224 ms |
83440 KB |
Output is correct |
3 |
Correct |
1162 ms |
83584 KB |
Output is correct |
4 |
Correct |
1028 ms |
83464 KB |
Output is correct |
5 |
Correct |
1048 ms |
83492 KB |
Output is correct |
6 |
Correct |
1026 ms |
83328 KB |
Output is correct |
7 |
Correct |
1069 ms |
83484 KB |
Output is correct |
8 |
Correct |
1103 ms |
83432 KB |
Output is correct |
9 |
Correct |
1131 ms |
83472 KB |
Output is correct |
10 |
Correct |
1091 ms |
83408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
32140 KB |
Output is correct |
2 |
Correct |
183 ms |
36592 KB |
Output is correct |
3 |
Correct |
1018 ms |
83464 KB |
Output is correct |
4 |
Correct |
2057 ms |
83532 KB |
Output is correct |
5 |
Correct |
1054 ms |
96576 KB |
Output is correct |
6 |
Correct |
2214 ms |
134284 KB |
Output is correct |
7 |
Correct |
1083 ms |
89328 KB |
Output is correct |
8 |
Correct |
1208 ms |
83588 KB |
Output is correct |
9 |
Correct |
1107 ms |
83868 KB |
Output is correct |
10 |
Correct |
1127 ms |
88236 KB |
Output is correct |
11 |
Correct |
1084 ms |
106908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
32584 KB |
Output is correct |
2 |
Correct |
181 ms |
33300 KB |
Output is correct |
3 |
Correct |
231 ms |
33228 KB |
Output is correct |
4 |
Correct |
296 ms |
33380 KB |
Output is correct |
5 |
Correct |
448 ms |
33868 KB |
Output is correct |
6 |
Correct |
1597 ms |
97540 KB |
Output is correct |
7 |
Correct |
1796 ms |
97524 KB |
Output is correct |
8 |
Correct |
1595 ms |
97608 KB |
Output is correct |
9 |
Correct |
2673 ms |
97612 KB |
Output is correct |
10 |
Correct |
1474 ms |
97504 KB |
Output is correct |
11 |
Correct |
1532 ms |
97708 KB |
Output is correct |
12 |
Correct |
1467 ms |
97452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
31680 KB |
Output is correct |
2 |
Correct |
42 ms |
31732 KB |
Output is correct |
3 |
Correct |
50 ms |
31760 KB |
Output is correct |
4 |
Correct |
39 ms |
31712 KB |
Output is correct |
5 |
Correct |
36 ms |
31728 KB |
Output is correct |
6 |
Correct |
48 ms |
31692 KB |
Output is correct |
7 |
Correct |
52 ms |
31856 KB |
Output is correct |
8 |
Correct |
47 ms |
31732 KB |
Output is correct |
9 |
Correct |
46 ms |
31756 KB |
Output is correct |
10 |
Correct |
50 ms |
31828 KB |
Output is correct |
11 |
Correct |
47 ms |
31728 KB |
Output is correct |
12 |
Correct |
36 ms |
31732 KB |
Output is correct |
13 |
Correct |
91 ms |
32276 KB |
Output is correct |
14 |
Correct |
106 ms |
32340 KB |
Output is correct |
15 |
Correct |
71 ms |
32424 KB |
Output is correct |
16 |
Correct |
62 ms |
32832 KB |
Output is correct |
17 |
Correct |
82 ms |
32356 KB |
Output is correct |
18 |
Correct |
77 ms |
32328 KB |
Output is correct |
19 |
Correct |
76 ms |
32360 KB |
Output is correct |
20 |
Correct |
76 ms |
32460 KB |
Output is correct |
21 |
Correct |
66 ms |
32500 KB |
Output is correct |
22 |
Correct |
57 ms |
32832 KB |
Output is correct |
23 |
Correct |
2057 ms |
67488 KB |
Output is correct |
24 |
Correct |
1224 ms |
83440 KB |
Output is correct |
25 |
Correct |
1162 ms |
83584 KB |
Output is correct |
26 |
Correct |
1028 ms |
83464 KB |
Output is correct |
27 |
Correct |
1048 ms |
83492 KB |
Output is correct |
28 |
Correct |
1026 ms |
83328 KB |
Output is correct |
29 |
Correct |
1069 ms |
83484 KB |
Output is correct |
30 |
Correct |
1103 ms |
83432 KB |
Output is correct |
31 |
Correct |
1131 ms |
83472 KB |
Output is correct |
32 |
Correct |
1091 ms |
83408 KB |
Output is correct |
33 |
Correct |
86 ms |
32140 KB |
Output is correct |
34 |
Correct |
183 ms |
36592 KB |
Output is correct |
35 |
Correct |
1018 ms |
83464 KB |
Output is correct |
36 |
Correct |
2057 ms |
83532 KB |
Output is correct |
37 |
Correct |
1054 ms |
96576 KB |
Output is correct |
38 |
Correct |
2214 ms |
134284 KB |
Output is correct |
39 |
Correct |
1083 ms |
89328 KB |
Output is correct |
40 |
Correct |
1208 ms |
83588 KB |
Output is correct |
41 |
Correct |
1107 ms |
83868 KB |
Output is correct |
42 |
Correct |
1127 ms |
88236 KB |
Output is correct |
43 |
Correct |
1084 ms |
106908 KB |
Output is correct |
44 |
Correct |
161 ms |
32584 KB |
Output is correct |
45 |
Correct |
181 ms |
33300 KB |
Output is correct |
46 |
Correct |
231 ms |
33228 KB |
Output is correct |
47 |
Correct |
296 ms |
33380 KB |
Output is correct |
48 |
Correct |
448 ms |
33868 KB |
Output is correct |
49 |
Correct |
1597 ms |
97540 KB |
Output is correct |
50 |
Correct |
1796 ms |
97524 KB |
Output is correct |
51 |
Correct |
1595 ms |
97608 KB |
Output is correct |
52 |
Correct |
2673 ms |
97612 KB |
Output is correct |
53 |
Correct |
1474 ms |
97504 KB |
Output is correct |
54 |
Correct |
1532 ms |
97708 KB |
Output is correct |
55 |
Correct |
1467 ms |
97452 KB |
Output is correct |
56 |
Correct |
197 ms |
33288 KB |
Output is correct |
57 |
Correct |
384 ms |
33296 KB |
Output is correct |
58 |
Correct |
600 ms |
33792 KB |
Output is correct |
59 |
Correct |
1935 ms |
84516 KB |
Output is correct |
60 |
Correct |
3257 ms |
84588 KB |
Output is correct |
61 |
Correct |
1831 ms |
84548 KB |
Output is correct |
62 |
Correct |
1610 ms |
91556 KB |
Output is correct |
63 |
Correct |
3058 ms |
90344 KB |
Output is correct |
64 |
Correct |
2058 ms |
85912 KB |
Output is correct |
65 |
Correct |
2094 ms |
84580 KB |
Output is correct |
66 |
Correct |
2359 ms |
84788 KB |
Output is correct |
67 |
Correct |
2322 ms |
89172 KB |
Output is correct |
68 |
Correct |
1741 ms |
98744 KB |
Output is correct |
69 |
Correct |
2904 ms |
107812 KB |
Output is correct |