// Iterative segtree implementation makes it easy to implement yay
#include "doll.h"
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
const int inf = 1e9, N = 1 << 18;
int t[N << 1], r[N];
void create_circuit(int m, vector<int> a) {
a.eb(0); int n = a.size(), sz = 1;
while (sz < n) sz <<= 1;
rep(i, 0, sz) t[i + sz] = inf;
for (int i = 0, j = 0; i < sz; ++i) {
r[i] = r[i >> 1];
if (i & 1) r[i] |= sz;
r[i] >>= 1;
if (sz - n <= r[i])
t[r[i] + sz] = a[j++];
}
int rt = 0;
vector<int> x, y;
for (int i = sz; --i; )
if (t[i << 1|0] != t[i << 1|1]) {
t[i] = --rt;
x.eb(t[i << 1|0]);
y.eb(t[i << 1|1]);
} else t[i] = t[i << 1];
rep(i, 0, -rt) {
if (x[i] == inf) x[i] = rt;
if (y[i] == inf) y[i] = rt;
}
answer(vector<int>(m + 1, rt), x, y);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
37 ms |
5524 KB |
Output is correct |
3 |
Correct |
32 ms |
5328 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
12 ms |
1100 KB |
Output is correct |
6 |
Correct |
64 ms |
7160 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
37 ms |
5524 KB |
Output is correct |
3 |
Correct |
32 ms |
5328 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
12 ms |
1100 KB |
Output is correct |
6 |
Correct |
64 ms |
7160 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
116 ms |
8640 KB |
Output is correct |
9 |
Correct |
59 ms |
9160 KB |
Output is correct |
10 |
Correct |
83 ms |
11516 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
37 ms |
5524 KB |
Output is correct |
3 |
Correct |
32 ms |
5328 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
12 ms |
1100 KB |
Output is correct |
6 |
Correct |
64 ms |
7160 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
116 ms |
8640 KB |
Output is correct |
9 |
Correct |
59 ms |
9160 KB |
Output is correct |
10 |
Correct |
83 ms |
11516 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
80 ms |
10896 KB |
Output is correct |
15 |
Correct |
53 ms |
8128 KB |
Output is correct |
16 |
Correct |
143 ms |
10672 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
82 ms |
11116 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
47 ms |
4296 KB |
Output is correct |
3 |
Correct |
20 ms |
4296 KB |
Output is correct |
4 |
Correct |
65 ms |
4908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
47 ms |
4296 KB |
Output is correct |
3 |
Correct |
20 ms |
4296 KB |
Output is correct |
4 |
Correct |
65 ms |
4908 KB |
Output is correct |
5 |
Correct |
79 ms |
10492 KB |
Output is correct |
6 |
Correct |
75 ms |
10108 KB |
Output is correct |
7 |
Correct |
76 ms |
10240 KB |
Output is correct |
8 |
Correct |
74 ms |
9852 KB |
Output is correct |
9 |
Correct |
39 ms |
7352 KB |
Output is correct |
10 |
Correct |
69 ms |
9140 KB |
Output is correct |
11 |
Correct |
69 ms |
9524 KB |
Output is correct |
12 |
Correct |
50 ms |
8728 KB |
Output is correct |
13 |
Correct |
57 ms |
7696 KB |
Output is correct |
14 |
Correct |
63 ms |
7876 KB |
Output is correct |
15 |
Correct |
65 ms |
7904 KB |
Output is correct |
16 |
Correct |
3 ms |
568 KB |
Output is correct |
17 |
Correct |
64 ms |
7188 KB |
Output is correct |
18 |
Correct |
47 ms |
8592 KB |
Output is correct |
19 |
Correct |
50 ms |
8644 KB |
Output is correct |
20 |
Correct |
76 ms |
9704 KB |
Output is correct |
21 |
Correct |
78 ms |
9648 KB |
Output is correct |
22 |
Correct |
82 ms |
9648 KB |
Output is correct |