# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
791580 |
2023-07-24T07:39:51 Z |
GEN 이지후(#10078) |
Sličnost (COI23_slicnost) |
C++17 |
|
3000 ms |
26692 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 270000;
pi operator+(pi a, pi b) {
if (a > b)
swap(a, b);
if (b[0] == a[0])
b[1] += a[1];
return b;
}
struct seg {
pi tree[MAXT];
int lazy[MAXT];
void lazydown(int p) {
for (int i = 2 * p; i < 2 * p + 2; i++) {
lazy[i] += lazy[p];
tree[i][0] += lazy[p];
}
lazy[p] = 0;
}
void init(int s, int e, int p) {
if (s == e) {
tree[p] = {0, 1};
return;
}
int m = (s + e) / 2;
init(s, m, 2 * p);
init(m + 1, e, 2 * p + 1);
tree[p] = tree[2 * p] + tree[2 * p + 1];
}
void add(int s, int e, int ps, int pe, int p, int v) {
if (e < ps || pe < s)
return;
if (s <= ps && pe <= e) {
lazy[p] += v;
tree[p][0] += v;
return;
}
lazydown(p);
int pm = (ps + pe) / 2;
add(s, e, ps, pm, 2 * p, v);
add(s, e, pm + 1, pe, 2 * p + 1, v);
tree[p] = tree[2 * p] + tree[2 * p + 1];
}
pi query() { return tree[1]; }
} seg;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, q;
cin >> n >> k >> q;
vector<int> a1(n), a2(n);
vector<int> r1(n), r2(n);
for (int i = 0; i < n; i++) {
cin >> a1[i];
a1[i]--;
r1[a1[i]] = i;
}
for (int i = 0; i < n; i++) {
cin >> a2[i];
a2[i]--;
r2[a2[i]] = i;
}
vector<vector<array<int, 3>>> swp(n + 1);
vector<vector<array<int, 4>>> temp(n + 1);
vector<pi> queries(q + 1);
for (int i = 0; i < n; i++) {
int x1 = max(k - 1, r1[i]), x2 = min(r1[i] + k, n);
int y1 = max(k - 1, r2[i]), y2 = min(r2[i] + k, n);
swp[x1].push_back({y1, y2, +1});
swp[x2].push_back({y1, y2, -1});
}
auto rangeAdd = [&](int p, int l, int r, int d, int ts) {
if (p < k - 1 || p >= n)
return;
l = max(l, k - 1);
r = min(r, n);
temp[p].push_back({ts, l, r, d});
};
for (int i = 1; i <= q; i++) {
int t;
cin >> t;
t--;
int p1 = a1[t], p2 = a1[t + 1];
swap(a1[t], a1[t + 1]);
rangeAdd(r1[p1], r2[p1], r2[p1] + k, -1, i);
rangeAdd(r1[p1] + k, r2[p1], r2[p1] + k, +1, i);
rangeAdd(r1[p2] + k - 1, r2[p2], r2[p2] + k, -1, i);
rangeAdd(r1[p2] - 1, r2[p2], r2[p2] + k, +1, i);
r1[p1]++;
r1[p2]--;
}
seg.init(k - 1, n - 1, 1);
auto rangeAdd2 = [&](int l, int r, int d) { seg.add(l, r - 1, k - 1, n - 1, 1, d); };
auto query = [&]() { return seg.tree[1]; };
for (int i = k - 1; i < n; i++) {
for (auto &x : swp[i]) {
rangeAdd2(x[0], x[1], x[2]);
}
temp[i].push_back({q + 1, 0, 0});
int las = 0;
for (auto &[ts, l, r, d] : temp[i]) {
auto [mx, mxc] = query();
for (int t = las; t < ts; t++) {
if (queries[t][0] < mx) {
queries[t][0] = mx;
queries[t][1] = 0;
}
if (queries[t][0] == mx)
queries[t][1] += mxc;
}
las = ts;
rangeAdd2(l, r, d);
}
for (auto &[ts, l, r, d] : temp[i]) {
rangeAdd2(l, r, -d);
}
}
for (int i = 0; i <= q; i++) {
if (queries[i][0] == 0)
queries[i][1] = 1ll * (n - k + 1) * (n - k + 1);
cout << queries[i][0] << " " << queries[i][1] << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
1236 KB |
Output is correct |
18 |
Correct |
2 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
5 ms |
1256 KB |
Output is correct |
21 |
Correct |
4 ms |
1236 KB |
Output is correct |
22 |
Correct |
1 ms |
852 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
4 ms |
1236 KB |
Output is correct |
25 |
Correct |
4 ms |
980 KB |
Output is correct |
26 |
Correct |
4 ms |
1032 KB |
Output is correct |
27 |
Correct |
5 ms |
1236 KB |
Output is correct |
28 |
Correct |
3 ms |
980 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
1236 KB |
Output is correct |
18 |
Correct |
2 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
5 ms |
1256 KB |
Output is correct |
21 |
Correct |
4 ms |
1236 KB |
Output is correct |
22 |
Correct |
1 ms |
852 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
4 ms |
1236 KB |
Output is correct |
25 |
Correct |
4 ms |
980 KB |
Output is correct |
26 |
Correct |
4 ms |
1032 KB |
Output is correct |
27 |
Correct |
5 ms |
1236 KB |
Output is correct |
28 |
Correct |
3 ms |
980 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
852 KB |
Output is correct |
31 |
Correct |
81 ms |
17584 KB |
Output is correct |
32 |
Correct |
101 ms |
17664 KB |
Output is correct |
33 |
Correct |
17 ms |
8888 KB |
Output is correct |
34 |
Correct |
75 ms |
13196 KB |
Output is correct |
35 |
Correct |
130 ms |
17844 KB |
Output is correct |
36 |
Correct |
91 ms |
17188 KB |
Output is correct |
37 |
Correct |
19 ms |
9368 KB |
Output is correct |
38 |
Correct |
132 ms |
17488 KB |
Output is correct |
39 |
Correct |
107 ms |
17792 KB |
Output is correct |
40 |
Correct |
79 ms |
13440 KB |
Output is correct |
41 |
Correct |
91 ms |
16596 KB |
Output is correct |
42 |
Correct |
131 ms |
17128 KB |
Output is correct |
43 |
Correct |
80 ms |
13192 KB |
Output is correct |
44 |
Correct |
52 ms |
12888 KB |
Output is correct |
45 |
Correct |
21 ms |
9396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
0 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
1236 KB |
Output is correct |
18 |
Correct |
2 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
5 ms |
1256 KB |
Output is correct |
21 |
Correct |
4 ms |
1236 KB |
Output is correct |
22 |
Correct |
1 ms |
852 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
4 ms |
1236 KB |
Output is correct |
25 |
Correct |
4 ms |
980 KB |
Output is correct |
26 |
Correct |
4 ms |
1032 KB |
Output is correct |
27 |
Correct |
5 ms |
1236 KB |
Output is correct |
28 |
Correct |
3 ms |
980 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
852 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
0 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
0 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
0 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
1 ms |
340 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
34 ms |
1860 KB |
Output is correct |
47 |
Correct |
33 ms |
1828 KB |
Output is correct |
48 |
Correct |
2 ms |
980 KB |
Output is correct |
49 |
Correct |
16 ms |
1364 KB |
Output is correct |
50 |
Correct |
33 ms |
1824 KB |
Output is correct |
51 |
Correct |
6 ms |
980 KB |
Output is correct |
52 |
Correct |
23 ms |
1492 KB |
Output is correct |
53 |
Correct |
30 ms |
1736 KB |
Output is correct |
54 |
Correct |
36 ms |
1776 KB |
Output is correct |
55 |
Correct |
12 ms |
1352 KB |
Output is correct |
56 |
Correct |
32 ms |
1876 KB |
Output is correct |
57 |
Correct |
30 ms |
1772 KB |
Output is correct |
58 |
Correct |
8 ms |
1108 KB |
Output is correct |
59 |
Correct |
31 ms |
1476 KB |
Output is correct |
60 |
Correct |
7 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
1236 KB |
Output is correct |
18 |
Correct |
2 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
5 ms |
1256 KB |
Output is correct |
21 |
Correct |
4 ms |
1236 KB |
Output is correct |
22 |
Correct |
1 ms |
852 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
4 ms |
1236 KB |
Output is correct |
25 |
Correct |
4 ms |
980 KB |
Output is correct |
26 |
Correct |
4 ms |
1032 KB |
Output is correct |
27 |
Correct |
5 ms |
1236 KB |
Output is correct |
28 |
Correct |
3 ms |
980 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
852 KB |
Output is correct |
31 |
Correct |
81 ms |
17584 KB |
Output is correct |
32 |
Correct |
101 ms |
17664 KB |
Output is correct |
33 |
Correct |
17 ms |
8888 KB |
Output is correct |
34 |
Correct |
75 ms |
13196 KB |
Output is correct |
35 |
Correct |
130 ms |
17844 KB |
Output is correct |
36 |
Correct |
91 ms |
17188 KB |
Output is correct |
37 |
Correct |
19 ms |
9368 KB |
Output is correct |
38 |
Correct |
132 ms |
17488 KB |
Output is correct |
39 |
Correct |
107 ms |
17792 KB |
Output is correct |
40 |
Correct |
79 ms |
13440 KB |
Output is correct |
41 |
Correct |
91 ms |
16596 KB |
Output is correct |
42 |
Correct |
131 ms |
17128 KB |
Output is correct |
43 |
Correct |
80 ms |
13192 KB |
Output is correct |
44 |
Correct |
52 ms |
12888 KB |
Output is correct |
45 |
Correct |
21 ms |
9396 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
1 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
340 KB |
Output is correct |
51 |
Correct |
0 ms |
340 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
1 ms |
340 KB |
Output is correct |
54 |
Correct |
1 ms |
340 KB |
Output is correct |
55 |
Correct |
0 ms |
340 KB |
Output is correct |
56 |
Correct |
1 ms |
340 KB |
Output is correct |
57 |
Correct |
0 ms |
340 KB |
Output is correct |
58 |
Correct |
1 ms |
340 KB |
Output is correct |
59 |
Correct |
1 ms |
340 KB |
Output is correct |
60 |
Correct |
1 ms |
340 KB |
Output is correct |
61 |
Correct |
34 ms |
1860 KB |
Output is correct |
62 |
Correct |
33 ms |
1828 KB |
Output is correct |
63 |
Correct |
2 ms |
980 KB |
Output is correct |
64 |
Correct |
16 ms |
1364 KB |
Output is correct |
65 |
Correct |
33 ms |
1824 KB |
Output is correct |
66 |
Correct |
6 ms |
980 KB |
Output is correct |
67 |
Correct |
23 ms |
1492 KB |
Output is correct |
68 |
Correct |
30 ms |
1736 KB |
Output is correct |
69 |
Correct |
36 ms |
1776 KB |
Output is correct |
70 |
Correct |
12 ms |
1352 KB |
Output is correct |
71 |
Correct |
32 ms |
1876 KB |
Output is correct |
72 |
Correct |
30 ms |
1772 KB |
Output is correct |
73 |
Correct |
8 ms |
1108 KB |
Output is correct |
74 |
Correct |
31 ms |
1476 KB |
Output is correct |
75 |
Correct |
7 ms |
1108 KB |
Output is correct |
76 |
Execution timed out |
3084 ms |
26692 KB |
Time limit exceeded |
77 |
Halted |
0 ms |
0 KB |
- |