# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1036250 |
2024-07-27T07:06:33 Z |
ind1v |
Pilot (NOI19_pilot) |
C++11 |
|
429 ms |
53328 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct dsu {
int lab[N];
int cnt[N];
bool on[N];
long long cur;
dsu() {
memset(lab, -1, sizeof(lab));
fill(cnt, cnt + N, 1);
cur = 0;
}
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool merge(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return false;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
lab[u] += lab[v];
lab[v] = u;
cur -= 1LL * cnt[u] * (cnt[u] + 1) / 2;
cur -= 1LL * cnt[v] * (cnt[v] + 1) / 2;
cnt[u] += cnt[v];
cur += 1LL * cnt[u] * (cnt[u] + 1) / 2;
return true;
}
};
int n, q;
int h[N], y[N];
int ord_h[N], ord_y[N];
long long ans[N];
dsu g;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
for (int i = 1; i <= q; i++) {
cin >> y[i];
}
iota(ord_h + 1, ord_h + n + 1, 1);
sort(ord_h + 1, ord_h + n + 1, [](int u, int v) -> bool {
return h[u] < h[v];
});
iota(ord_y + 1, ord_y + q + 1, 1);
sort(ord_y + 1, ord_y + q + 1, [](int u, int v) -> bool {
return y[u] < y[v];
});
for (int i = 1, j = 1; i <= q; i++) {
while (j <= n && h[ord_h[j]] <= y[ord_y[i]]) {
g.on[ord_h[j]] = true;
g.cur++;
if (ord_h[j] - 1 >= 1 && g.on[ord_h[j] - 1]) {
g.merge(ord_h[j], ord_h[j] - 1);
}
if (ord_h[j] + 1 <= n && g.on[ord_h[j] + 1]) {
g.merge(ord_h[j], ord_h[j] + 1);
}
j++;
}
ans[ord_y[i]] = g.cur;
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8280 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8264 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8280 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8264 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8284 KB |
Output is correct |
20 |
Correct |
3 ms |
8280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8280 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8264 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8284 KB |
Output is correct |
20 |
Correct |
3 ms |
8280 KB |
Output is correct |
21 |
Correct |
4 ms |
8284 KB |
Output is correct |
22 |
Correct |
4 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8284 KB |
Output is correct |
24 |
Correct |
4 ms |
8344 KB |
Output is correct |
25 |
Correct |
6 ms |
8284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
9560 KB |
Output is correct |
2 |
Correct |
18 ms |
9816 KB |
Output is correct |
3 |
Correct |
17 ms |
9588 KB |
Output is correct |
4 |
Correct |
17 ms |
9640 KB |
Output is correct |
5 |
Correct |
21 ms |
9780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
12664 KB |
Output is correct |
2 |
Correct |
29 ms |
12792 KB |
Output is correct |
3 |
Correct |
29 ms |
12844 KB |
Output is correct |
4 |
Correct |
28 ms |
12628 KB |
Output is correct |
5 |
Correct |
28 ms |
12628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
12628 KB |
Output is correct |
2 |
Correct |
29 ms |
12816 KB |
Output is correct |
3 |
Correct |
29 ms |
12880 KB |
Output is correct |
4 |
Correct |
29 ms |
12628 KB |
Output is correct |
5 |
Correct |
30 ms |
12924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
21 ms |
9560 KB |
Output is correct |
12 |
Correct |
18 ms |
9816 KB |
Output is correct |
13 |
Correct |
17 ms |
9588 KB |
Output is correct |
14 |
Correct |
17 ms |
9640 KB |
Output is correct |
15 |
Correct |
21 ms |
9780 KB |
Output is correct |
16 |
Correct |
20 ms |
9564 KB |
Output is correct |
17 |
Correct |
16 ms |
9660 KB |
Output is correct |
18 |
Correct |
16 ms |
9820 KB |
Output is correct |
19 |
Correct |
14 ms |
9524 KB |
Output is correct |
20 |
Correct |
16 ms |
9820 KB |
Output is correct |
21 |
Correct |
17 ms |
9564 KB |
Output is correct |
22 |
Correct |
16 ms |
9564 KB |
Output is correct |
23 |
Correct |
16 ms |
9712 KB |
Output is correct |
24 |
Correct |
15 ms |
9560 KB |
Output is correct |
25 |
Correct |
16 ms |
9560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8280 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8264 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8284 KB |
Output is correct |
20 |
Correct |
3 ms |
8280 KB |
Output is correct |
21 |
Correct |
4 ms |
8284 KB |
Output is correct |
22 |
Correct |
4 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8284 KB |
Output is correct |
24 |
Correct |
4 ms |
8344 KB |
Output is correct |
25 |
Correct |
6 ms |
8284 KB |
Output is correct |
26 |
Correct |
21 ms |
9560 KB |
Output is correct |
27 |
Correct |
18 ms |
9816 KB |
Output is correct |
28 |
Correct |
17 ms |
9588 KB |
Output is correct |
29 |
Correct |
17 ms |
9640 KB |
Output is correct |
30 |
Correct |
21 ms |
9780 KB |
Output is correct |
31 |
Correct |
28 ms |
12664 KB |
Output is correct |
32 |
Correct |
29 ms |
12792 KB |
Output is correct |
33 |
Correct |
29 ms |
12844 KB |
Output is correct |
34 |
Correct |
28 ms |
12628 KB |
Output is correct |
35 |
Correct |
28 ms |
12628 KB |
Output is correct |
36 |
Correct |
29 ms |
12628 KB |
Output is correct |
37 |
Correct |
29 ms |
12816 KB |
Output is correct |
38 |
Correct |
29 ms |
12880 KB |
Output is correct |
39 |
Correct |
29 ms |
12628 KB |
Output is correct |
40 |
Correct |
30 ms |
12924 KB |
Output is correct |
41 |
Correct |
20 ms |
9564 KB |
Output is correct |
42 |
Correct |
16 ms |
9660 KB |
Output is correct |
43 |
Correct |
16 ms |
9820 KB |
Output is correct |
44 |
Correct |
14 ms |
9524 KB |
Output is correct |
45 |
Correct |
16 ms |
9820 KB |
Output is correct |
46 |
Correct |
17 ms |
9564 KB |
Output is correct |
47 |
Correct |
16 ms |
9564 KB |
Output is correct |
48 |
Correct |
16 ms |
9712 KB |
Output is correct |
49 |
Correct |
15 ms |
9560 KB |
Output is correct |
50 |
Correct |
16 ms |
9560 KB |
Output is correct |
51 |
Correct |
37 ms |
12628 KB |
Output is correct |
52 |
Correct |
37 ms |
12368 KB |
Output is correct |
53 |
Correct |
36 ms |
12508 KB |
Output is correct |
54 |
Correct |
37 ms |
12512 KB |
Output is correct |
55 |
Correct |
36 ms |
12368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8280 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8296 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8192 KB |
Output is correct |
9 |
Correct |
3 ms |
8280 KB |
Output is correct |
10 |
Correct |
4 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8280 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8264 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8284 KB |
Output is correct |
20 |
Correct |
3 ms |
8280 KB |
Output is correct |
21 |
Correct |
4 ms |
8284 KB |
Output is correct |
22 |
Correct |
4 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8284 KB |
Output is correct |
24 |
Correct |
4 ms |
8344 KB |
Output is correct |
25 |
Correct |
6 ms |
8284 KB |
Output is correct |
26 |
Correct |
21 ms |
9560 KB |
Output is correct |
27 |
Correct |
18 ms |
9816 KB |
Output is correct |
28 |
Correct |
17 ms |
9588 KB |
Output is correct |
29 |
Correct |
17 ms |
9640 KB |
Output is correct |
30 |
Correct |
21 ms |
9780 KB |
Output is correct |
31 |
Correct |
28 ms |
12664 KB |
Output is correct |
32 |
Correct |
29 ms |
12792 KB |
Output is correct |
33 |
Correct |
29 ms |
12844 KB |
Output is correct |
34 |
Correct |
28 ms |
12628 KB |
Output is correct |
35 |
Correct |
28 ms |
12628 KB |
Output is correct |
36 |
Correct |
29 ms |
12628 KB |
Output is correct |
37 |
Correct |
29 ms |
12816 KB |
Output is correct |
38 |
Correct |
29 ms |
12880 KB |
Output is correct |
39 |
Correct |
29 ms |
12628 KB |
Output is correct |
40 |
Correct |
30 ms |
12924 KB |
Output is correct |
41 |
Correct |
20 ms |
9564 KB |
Output is correct |
42 |
Correct |
16 ms |
9660 KB |
Output is correct |
43 |
Correct |
16 ms |
9820 KB |
Output is correct |
44 |
Correct |
14 ms |
9524 KB |
Output is correct |
45 |
Correct |
16 ms |
9820 KB |
Output is correct |
46 |
Correct |
17 ms |
9564 KB |
Output is correct |
47 |
Correct |
16 ms |
9564 KB |
Output is correct |
48 |
Correct |
16 ms |
9712 KB |
Output is correct |
49 |
Correct |
15 ms |
9560 KB |
Output is correct |
50 |
Correct |
16 ms |
9560 KB |
Output is correct |
51 |
Correct |
37 ms |
12628 KB |
Output is correct |
52 |
Correct |
37 ms |
12368 KB |
Output is correct |
53 |
Correct |
36 ms |
12508 KB |
Output is correct |
54 |
Correct |
37 ms |
12512 KB |
Output is correct |
55 |
Correct |
36 ms |
12368 KB |
Output is correct |
56 |
Correct |
429 ms |
52636 KB |
Output is correct |
57 |
Correct |
408 ms |
51536 KB |
Output is correct |
58 |
Correct |
371 ms |
49536 KB |
Output is correct |
59 |
Correct |
392 ms |
50516 KB |
Output is correct |
60 |
Correct |
389 ms |
53328 KB |
Output is correct |