# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
799329 |
2023-07-31T12:43:44 Z |
prvocislo |
Seats (IOI18_seats) |
C++17 |
|
3347 ms |
135652 KB |
#include "seats.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1 << 20;
vector<int> add(maxn * 2), il(maxn * 2), ir(maxn * 2);
vector<pair<int, int> > st(maxn * 2); // minimum v tomto vrchole a pocet tych minim
pair<int, int> merge(pair<int, int> a, pair<int, int> b)
{
if (a.first == b.first) return make_pair(a.first, a.second + b.second);
return min(a, b);
}
void upd(int li, int ri, int d, int vr = 1)
{
if (li > ri || ri < il[vr] || ir[vr] < li) return;
if (li <= il[vr] && ir[vr] <= ri)
{
st[vr].first += d, add[vr] += d;
return;
}
upd(li, ri, d, (vr << 1)), upd(li, ri, d, (vr << 1) | 1);
st[vr] = merge(st[vr << 1], st[(vr << 1) | 1]);
st[vr].first += add[vr];
}
int nr, nc;
vector<int> r, c;
vector<vector<int> > num;
void do2x2(int i, int j, int d) // spracuje stvorec [i, i+1], [j, j+1]
{
vector<int> v;
for (int ri = i; ri <= i + 1; ri++) for (int cj = j; cj <= j + 1; cj++)
{
if (ri >= 0 && cj >= 0 && ri < nr && cj < nc) v.push_back(num[ri][cj]);
else v.push_back(nr * nc);
}
sort(v.begin(), v.end());
upd(v[0], v[1] - 1, d), upd(v[2], v[3] - 1, d);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
for (int i = maxn; i < maxn * 2; i++)
{
il[i] = ir[i] = i - maxn;
if (i - maxn < H * W) st[i] = { 0, 1 };
else st[i] = { 1000'000'000, 1 };
}
for (int i = maxn - 1; i > 0; i--) il[i] = il[i << 1], ir[i] = ir[(i << 1) | 1], st[i] = merge(st[i << 1], st[(i << 1) | 1]);
nr = H, nc = W;
r = R, c = C;
num.assign(nr, vector<int>(nc, 0));
for (int i = 0; i < nr * nc; i++) num[r[i]][c[i]] = i;
for (int i = -1; i < nr; i++) for (int j = -1; j < nc; j++) do2x2(i, j, 1);
}
int swap_seats(int a, int b)
{
set<pair<int, int> > s;
for (int i = r[a] - 1; i <= r[a]; i++) for (int j = c[a] - 1; j <= c[a]; j++) s.insert({ i, j });
for (int i = r[b] - 1; i <= r[b]; i++) for (int j = c[b] - 1; j <= c[b]; j++) s.insert({ i, j });
for (pair<int, int> i : s) do2x2(i.first, i.second, -1);
swap(num[r[a]][c[a]], num[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (pair<int, int> i : s) do2x2(i.first, i.second, 1);
if (st[1].first == 4) return st[1].second;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
41428 KB |
Output is correct |
2 |
Correct |
64 ms |
41500 KB |
Output is correct |
3 |
Correct |
72 ms |
41444 KB |
Output is correct |
4 |
Correct |
56 ms |
41472 KB |
Output is correct |
5 |
Correct |
53 ms |
41548 KB |
Output is correct |
6 |
Correct |
64 ms |
41420 KB |
Output is correct |
7 |
Correct |
67 ms |
41472 KB |
Output is correct |
8 |
Correct |
65 ms |
41484 KB |
Output is correct |
9 |
Correct |
66 ms |
41444 KB |
Output is correct |
10 |
Correct |
67 ms |
41468 KB |
Output is correct |
11 |
Correct |
65 ms |
41500 KB |
Output is correct |
12 |
Correct |
52 ms |
41492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
41428 KB |
Output is correct |
2 |
Correct |
64 ms |
41500 KB |
Output is correct |
3 |
Correct |
72 ms |
41444 KB |
Output is correct |
4 |
Correct |
56 ms |
41472 KB |
Output is correct |
5 |
Correct |
53 ms |
41548 KB |
Output is correct |
6 |
Correct |
64 ms |
41420 KB |
Output is correct |
7 |
Correct |
67 ms |
41472 KB |
Output is correct |
8 |
Correct |
65 ms |
41484 KB |
Output is correct |
9 |
Correct |
66 ms |
41444 KB |
Output is correct |
10 |
Correct |
67 ms |
41468 KB |
Output is correct |
11 |
Correct |
65 ms |
41500 KB |
Output is correct |
12 |
Correct |
52 ms |
41492 KB |
Output is correct |
13 |
Correct |
95 ms |
41844 KB |
Output is correct |
14 |
Correct |
107 ms |
41744 KB |
Output is correct |
15 |
Correct |
75 ms |
41872 KB |
Output is correct |
16 |
Correct |
62 ms |
42324 KB |
Output is correct |
17 |
Correct |
89 ms |
41884 KB |
Output is correct |
18 |
Correct |
80 ms |
41840 KB |
Output is correct |
19 |
Correct |
79 ms |
41868 KB |
Output is correct |
20 |
Correct |
73 ms |
42080 KB |
Output is correct |
21 |
Correct |
63 ms |
41884 KB |
Output is correct |
22 |
Correct |
64 ms |
42348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2008 ms |
84780 KB |
Output is correct |
2 |
Correct |
948 ms |
84788 KB |
Output is correct |
3 |
Correct |
953 ms |
84780 KB |
Output is correct |
4 |
Correct |
734 ms |
84784 KB |
Output is correct |
5 |
Correct |
787 ms |
84788 KB |
Output is correct |
6 |
Correct |
754 ms |
84796 KB |
Output is correct |
7 |
Correct |
868 ms |
84888 KB |
Output is correct |
8 |
Correct |
964 ms |
84784 KB |
Output is correct |
9 |
Correct |
907 ms |
84704 KB |
Output is correct |
10 |
Correct |
838 ms |
84884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
41860 KB |
Output is correct |
2 |
Correct |
162 ms |
45252 KB |
Output is correct |
3 |
Correct |
782 ms |
84788 KB |
Output is correct |
4 |
Correct |
1983 ms |
84876 KB |
Output is correct |
5 |
Correct |
803 ms |
88720 KB |
Output is correct |
6 |
Correct |
1800 ms |
135652 KB |
Output is correct |
7 |
Correct |
763 ms |
86020 KB |
Output is correct |
8 |
Correct |
882 ms |
84752 KB |
Output is correct |
9 |
Correct |
947 ms |
85144 KB |
Output is correct |
10 |
Correct |
831 ms |
87912 KB |
Output is correct |
11 |
Correct |
818 ms |
108196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
42936 KB |
Output is correct |
2 |
Correct |
316 ms |
42952 KB |
Output is correct |
3 |
Correct |
343 ms |
43020 KB |
Output is correct |
4 |
Correct |
366 ms |
43088 KB |
Output is correct |
5 |
Correct |
450 ms |
43408 KB |
Output is correct |
6 |
Correct |
1304 ms |
89680 KB |
Output is correct |
7 |
Correct |
1502 ms |
89604 KB |
Output is correct |
8 |
Correct |
1246 ms |
89600 KB |
Output is correct |
9 |
Correct |
2885 ms |
89612 KB |
Output is correct |
10 |
Correct |
1232 ms |
89596 KB |
Output is correct |
11 |
Correct |
1281 ms |
89608 KB |
Output is correct |
12 |
Correct |
1195 ms |
89612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
41428 KB |
Output is correct |
2 |
Correct |
64 ms |
41500 KB |
Output is correct |
3 |
Correct |
72 ms |
41444 KB |
Output is correct |
4 |
Correct |
56 ms |
41472 KB |
Output is correct |
5 |
Correct |
53 ms |
41548 KB |
Output is correct |
6 |
Correct |
64 ms |
41420 KB |
Output is correct |
7 |
Correct |
67 ms |
41472 KB |
Output is correct |
8 |
Correct |
65 ms |
41484 KB |
Output is correct |
9 |
Correct |
66 ms |
41444 KB |
Output is correct |
10 |
Correct |
67 ms |
41468 KB |
Output is correct |
11 |
Correct |
65 ms |
41500 KB |
Output is correct |
12 |
Correct |
52 ms |
41492 KB |
Output is correct |
13 |
Correct |
95 ms |
41844 KB |
Output is correct |
14 |
Correct |
107 ms |
41744 KB |
Output is correct |
15 |
Correct |
75 ms |
41872 KB |
Output is correct |
16 |
Correct |
62 ms |
42324 KB |
Output is correct |
17 |
Correct |
89 ms |
41884 KB |
Output is correct |
18 |
Correct |
80 ms |
41840 KB |
Output is correct |
19 |
Correct |
79 ms |
41868 KB |
Output is correct |
20 |
Correct |
73 ms |
42080 KB |
Output is correct |
21 |
Correct |
63 ms |
41884 KB |
Output is correct |
22 |
Correct |
64 ms |
42348 KB |
Output is correct |
23 |
Correct |
2008 ms |
84780 KB |
Output is correct |
24 |
Correct |
948 ms |
84788 KB |
Output is correct |
25 |
Correct |
953 ms |
84780 KB |
Output is correct |
26 |
Correct |
734 ms |
84784 KB |
Output is correct |
27 |
Correct |
787 ms |
84788 KB |
Output is correct |
28 |
Correct |
754 ms |
84796 KB |
Output is correct |
29 |
Correct |
868 ms |
84888 KB |
Output is correct |
30 |
Correct |
964 ms |
84784 KB |
Output is correct |
31 |
Correct |
907 ms |
84704 KB |
Output is correct |
32 |
Correct |
838 ms |
84884 KB |
Output is correct |
33 |
Correct |
94 ms |
41860 KB |
Output is correct |
34 |
Correct |
162 ms |
45252 KB |
Output is correct |
35 |
Correct |
782 ms |
84788 KB |
Output is correct |
36 |
Correct |
1983 ms |
84876 KB |
Output is correct |
37 |
Correct |
803 ms |
88720 KB |
Output is correct |
38 |
Correct |
1800 ms |
135652 KB |
Output is correct |
39 |
Correct |
763 ms |
86020 KB |
Output is correct |
40 |
Correct |
882 ms |
84752 KB |
Output is correct |
41 |
Correct |
947 ms |
85144 KB |
Output is correct |
42 |
Correct |
831 ms |
87912 KB |
Output is correct |
43 |
Correct |
818 ms |
108196 KB |
Output is correct |
44 |
Correct |
303 ms |
42936 KB |
Output is correct |
45 |
Correct |
316 ms |
42952 KB |
Output is correct |
46 |
Correct |
343 ms |
43020 KB |
Output is correct |
47 |
Correct |
366 ms |
43088 KB |
Output is correct |
48 |
Correct |
450 ms |
43408 KB |
Output is correct |
49 |
Correct |
1304 ms |
89680 KB |
Output is correct |
50 |
Correct |
1502 ms |
89604 KB |
Output is correct |
51 |
Correct |
1246 ms |
89600 KB |
Output is correct |
52 |
Correct |
2885 ms |
89612 KB |
Output is correct |
53 |
Correct |
1232 ms |
89596 KB |
Output is correct |
54 |
Correct |
1281 ms |
89608 KB |
Output is correct |
55 |
Correct |
1195 ms |
89612 KB |
Output is correct |
56 |
Correct |
376 ms |
42984 KB |
Output is correct |
57 |
Correct |
575 ms |
43116 KB |
Output is correct |
58 |
Correct |
607 ms |
43288 KB |
Output is correct |
59 |
Correct |
1714 ms |
85740 KB |
Output is correct |
60 |
Correct |
3316 ms |
85752 KB |
Output is correct |
61 |
Correct |
1604 ms |
85772 KB |
Output is correct |
62 |
Correct |
1338 ms |
87624 KB |
Output is correct |
63 |
Correct |
3347 ms |
86944 KB |
Output is correct |
64 |
Correct |
1818 ms |
86092 KB |
Output is correct |
65 |
Correct |
1642 ms |
85756 KB |
Output is correct |
66 |
Correct |
1850 ms |
86104 KB |
Output is correct |
67 |
Correct |
1715 ms |
88908 KB |
Output is correct |
68 |
Correct |
1350 ms |
100056 KB |
Output is correct |
69 |
Correct |
2786 ms |
109260 KB |
Output is correct |