QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#23813 | #2970. Trade Routes | maze# | AC ✓ | 858ms | 85948kb | C++17 | 4.1kb | 2022-03-19 15:59:56 | 2022-04-30 04:10:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 300009, inf = 1e9 + 200309;
vector<int> e[N];
int fa[N], dep[N], sz[N], son[N], top[N], dfn[N], rk[N], cnt;
int a[N];
struct V {
ll val;
int id;
} v[N];
bool cmp(V x, V y) {
if (x.val == y.val) {
return x.id < y.id;
}
return x.val > y.val;
}
vector<int> ans;
struct Node {
int l, r;
int add;
int mn;
} tree[N << 2];
void pushup(int x) { tree[x].mn = min(tree[x << 1].mn, tree[x << 1 | 1].mn); }
void pushdown(int x) {
if (tree[x].add) {
tree[x << 1].mn += tree[x].add;
tree[x << 1 | 1].mn += tree[x].add;
tree[x << 1].add += tree[x].add;
tree[x << 1 | 1].add += tree[x].add;
tree[x].add = 0;
}
}
void build(int l, int r, int x) {
tree[x].l = l, tree[x].r = r;
tree[x].add = 0;
if (l == r) {
tree[x].mn = a[rk[l]];
return;
}
int mid = (l + r) >> 1;
build(l, mid, x << 1);
build(mid + 1, r, x << 1 | 1);
pushup(x);
}
void update(int l, int r, int x, int val) {
if (l <= tree[x].l && r >= tree[x].r) {
tree[x].mn += val;
tree[x].add += val;
return;
}
pushdown(x);
int mid = (tree[x].l + tree[x].r) >> 1;
if (l <= mid) {
update(l, r, x << 1, val);
}
if (r > mid) {
update(l, r, x << 1 | 1, val);
}
pushup(x);
}
int query(int l, int r, int x) {
if (l <= tree[x].l && r >= tree[x].r) {
return tree[x].mn;
}
pushdown(x);
int mid = (tree[x].l + tree[x].r) >> 1;
int ret = inf;
if (l <= mid) {
ret = min(query(l, r, x << 1), ret);
}
if (r > mid) {
ret = min(query(l, r, x << 1 | 1), ret);
}
return ret;
}
void dfs1(int x) {
son[x] = -1;
sz[x] = 1;
for (auto it : e[x]) {
dep[it] = dep[x] + 1;
dfs1(it);
sz[x] += sz[it];
if (son[x] == -1 || sz[it] > sz[son[x]])
son[x] = it;
}
}
void dfs2(int x, int t) {
top[x] = t;
++cnt;
dfn[x] = cnt;
rk[cnt] = x;
if (son[x] == -1)
return;
dfs2(son[x], t);
for (auto it : e[x]) {
if (it != son[x]) {
dfs2(it, it);
}
}
}
int querymn(int x, int y) {
int ret = inf, fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] >= dep[fy]) {
ret = min(ret, query(dfn[fx], dfn[x], 1)), x = fa[fx];
} else {
ret = min(ret, query(dfn[fy], dfn[y], 1)), y = fa[fy];
}
fx = top[x];
fy = top[y];
}
if (dfn[x] < dfn[y]) {
ret = min(ret, query(dfn[x], dfn[y], 1));
} else {
ret = min(ret, query(dfn[y], dfn[x], 1));
}
return ret;
}
void updatemn(int x, int y) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] >= dep[fy]) {
update(dfn[fx], dfn[x], 1, -1), x = fa[fx];
} else {
update(dfn[fy], dfn[y], 1, -1), y = fa[fy];
}
fx = top[x];
fy = top[y];
}
if (dfn[x] < dfn[y]) {
update(dfn[x], dfn[y], 1, -1);
} else {
update(dfn[y], dfn[x], 1, -1);
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
fa[1] = 0;
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
e[fa[i]].push_back(i);
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> v[i].val;
v[i].id = i;
}
sort(v + 1, v + n + 1, cmp);
dfs1(1);
dfs2(1, 1);
build(1, n, 1);
ll sum = 0;
for (int i = 1; i <= n; ++i) {
if (querymn(1, 1) <= 0)
break;
if (querymn(1, v[i].id) > 0) {
sum += v[i].val;
ans.push_back(v[i].id);
updatemn(1, v[i].id);
}
}
cout << sum << '\n';
cout << ans.size();
sort(ans.begin(), ans.end());
for (auto it : ans) {
cout << " " << it;
}
cout << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 23336kb
input:
7 1 1 2 2 3 3 2 1 2 1 1 1 1 6 5 3 8 4 7 1
output:
15 2 4 6
result:
ok good plan!
Test #2:
score: 0
Accepted
time: 2ms
memory: 22812kb
input:
9 1 1 2 3 3 4 4 4 4 4 2 4 1 0 1 1 1 100 30 10 0 50 200 12 15 13
output:
195 4 1 2 5 8
result:
ok good plan!
Test #3:
score: 0
Accepted
time: 0ms
memory: 23212kb
input:
2 1 1 1 0 1
output:
1 1 2
result:
ok good plan!
Test #4:
score: 0
Accepted
time: 2ms
memory: 22900kb
input:
2 1 1 1 1 0
output:
1 1 1
result:
ok good plan!
Test #5:
score: 0
Accepted
time: 2ms
memory: 22156kb
input:
2 1 1 0 0 1
output:
0 1 1
result:
ok good plan!
Test #6:
score: 0
Accepted
time: 8ms
memory: 22672kb
input:
2 1 1 0 2 3
output:
2 1 1
result:
ok good plan!
Test #7:
score: 0
Accepted
time: 2ms
memory: 22744kb
input:
2 1 1 0 1 0
output:
1 1 1
result:
ok good plan!
Test #8:
score: 0
Accepted
time: 508ms
memory: 64376kb
input:
300000 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
150046142356123 299998 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...
result:
ok good plan!
Test #9:
score: 0
Accepted
time: 459ms
memory: 65080kb
input:
299998 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
149753436119484 299996 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...
result:
ok good plan!
Test #10:
score: 0
Accepted
time: 107ms
memory: 84132kb
input:
300000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
1000000000 1 300000
result:
ok good plan!
Test #11:
score: 0
Accepted
time: 256ms
memory: 85948kb
input:
300000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
45999550001 300000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...
result:
ok good plan!
Test #12:
score: 0
Accepted
time: 250ms
memory: 43976kb
input:
300000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
112458998107940 150007 2 3 4 6 7 9 13 14 15 16 17 18 21 22 25 27 29 30 31 32 33 34 39 42 45 46 47 48 49 51 52 53 54 55 60 62 64 65 67 69 70 72 74 76 79 81 82 84 85 88 91 92 97 98 99 102 105 106 109 110 112 114 115 119 120 121 122 125 126 127 129 133 135 144 146 147 148 149 152 153 154 159 160 161 16...
result:
ok good plan!
Test #13:
score: 0
Accepted
time: 299ms
memory: 64816kb
input:
300000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
44999849955 299990 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
ok good plan!
Test #14:
score: 0
Accepted
time: 325ms
memory: 63640kb
input:
300000 1 1 2 3 3 5 5 7 8 9 9 11 12 13 14 15 16 17 17 19 19 21 21 23 23 25 25 27 28 28 30 30 32 32 34 35 36 36 38 39 40 40 42 42 44 44 46 47 48 48 50 51 52 53 53 55 55 57 57 59 60 61 61 63 64 65 65 67 68 68 70 71 72 72 74 74 76 77 77 79 79 81 82 82 84 84 86 87 88 88 90 91 91 93 94 94 96 96 98 98 100 ...
output:
119869570730285 165925 1 2 3 4 5 7 10 12 13 14 16 18 19 20 21 22 23 25 26 28 31 32 35 36 37 38 40 41 42 43 45 47 49 52 54 55 57 59 60 61 63 64 65 68 69 70 71 72 73 74 75 76 78 79 80 81 85 86 87 88 90 91 92 93 94 95 96 97 99 101 102 104 106 108 109 110 111 112 115 116 118 120 122 124 125 126 127 128 ...
result:
ok good plan!
Test #15:
score: 0
Accepted
time: 454ms
memory: 60060kb
input:
300000 1 1 1 3 4 5 6 6 8 8 10 11 11 13 14 14 14 17 17 19 19 19 22 23 23 25 26 26 28 28 28 31 31 33 34 35 35 37 37 39 39 39 42 43 43 43 46 47 48 48 50 51 51 51 54 54 56 56 58 58 58 61 61 61 64 65 65 65 68 68 70 70 70 73 74 75 75 75 78 78 78 81 81 81 84 84 86 86 86 89 89 91 91 93 94 95 95 95 98 98 100...
output:
128728176954188 187726 1 2 3 4 5 6 7 10 13 14 15 16 17 18 19 20 21 22 23 24 25 28 30 33 34 35 38 40 41 42 44 45 46 47 48 50 51 54 55 56 57 58 59 64 65 66 68 69 71 73 74 75 77 78 79 80 81 82 83 84 85 86 88 89 90 91 92 94 95 97 98 99 100 101 102 104 106 107 109 110 113 114 116 117 118 119 120 122 123 ...
result:
ok good plan!
Test #16:
score: 0
Accepted
time: 461ms
memory: 51280kb
input:
300000 1 1 1 1 1 1 1 1 1 9 9 9 12 12 12 12 12 12 12 12 12 12 22 22 22 22 22 22 22 29 29 29 32 32 32 32 32 32 32 32 40 40 40 40 44 44 44 44 44 49 49 49 49 49 49 49 49 49 58 58 58 58 58 58 58 58 58 67 68 68 68 68 68 68 68 75 75 75 75 79 80 80 80 80 80 80 86 86 86 86 86 86 86 86 86 86 96 96 96 96 96 10...
output:
145836766664662 250296 1 2 4 5 6 7 8 9 10 11 12 14 15 17 18 19 20 21 22 23 24 25 26 28 29 30 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 49 51 52 53 54 55 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 10...
result:
ok good plan!
Test #17:
score: 0
Accepted
time: 503ms
memory: 46356kb
input:
300000 1 1 1 1 1 1 1 1 1 1 1 1 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 93 93 93 93 93 93 93 93 93...
output:
149966532081162 293998 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...
result:
ok good plan!
Test #18:
score: 0
Accepted
time: 806ms
memory: 47192kb
input:
275471 1 2 1 4 1 6 4 4 1 5 9 8 1 4 7 9 4 9 8 1 1 19 18 22 23 18 6 23 3 4 31 19 3 7 30 24 7 5 11 15 23 18 29 13 43 6 26 12 6 7 28 30 4 52 3 43 1 40 34 25 14 42 55 33 7 47 54 17 36 6 52 11 25 61 63 33 28 1 33 59 1 36 2 17 31 42 69 45 60 61 72 78 26 60 71 6 12 92 43 97 3 30 100 87 27 28 60 36 33 73 36 ...
output:
135892585453332 250552 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...
result:
ok good plan!
Test #19:
score: 0
Accepted
time: 855ms
memory: 49584kb
input:
296959 1 2 2 3 5 3 6 1 8 10 7 1 8 14 8 1 16 2 2 4 5 15 1 3 7 19 8 12 11 27 23 14 28 21 2 20 9 34 28 18 8 38 38 25 12 23 30 9 13 34 33 18 20 24 34 7 46 9 12 50 58 4 47 21 4 61 56 43 12 14 66 17 58 15 4 71 29 67 13 13 16 7 65 49 70 86 80 28 11 80 86 13 90 19 14 90 69 61 9 70 90 25 36 80 4 103 45 33 14...
output:
146350546357477 270349 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 9...
result:
ok good plan!
Test #20:
score: 0
Accepted
time: 824ms
memory: 47124kb
input:
278895 1 2 1 2 5 2 7 4 7 4 7 4 5 5 10 12 14 9 9 16 13 17 13 2 19 18 22 21 11 15 2 8 14 32 25 16 16 7 27 5 33 22 27 11 8 24 24 21 25 33 26 37 22 3 15 24 4 54 20 25 8 16 42 10 62 8 13 43 14 11 11 26 9 39 35 39 14 11 68 13 10 39 5 72 57 39 25 31 43 62 62 16 66 30 38 70 93 87 95 83 3 57 31 15 17 55 40 5...
output:
137707025187012 253432 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
result:
ok good plan!
Test #21:
score: 0
Accepted
time: 799ms
memory: 48184kb
input:
282092 1 1 2 2 1 5 6 3 9 2 11 11 10 8 7 8 11 3 8 8 4 4 22 1 11 24 25 14 28 18 21 26 16 21 8 6 34 4 8 6 32 2 6 20 14 16 44 33 30 25 43 19 25 42 9 36 30 31 2 50 34 9 16 16 52 61 46 5 56 40 1 70 56 48 35 72 9 13 27 6 9 76 78 50 82 21 54 45 82 69 54 6 1 27 86 67 39 55 98 88 36 90 25 43 43 105 28 107 56 ...
output:
139182553954761 256779 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 43 44 45 46 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...
result:
ok good plan!
Test #22:
score: 0
Accepted
time: 774ms
memory: 46196kb
input:
271142 1 1 2 4 1 6 6 3 3 1 10 3 10 14 9 12 13 15 9 10 19 1 17 19 18 14 13 18 1 30 10 29 31 16 31 13 18 26 23 5 31 33 42 15 43 37 8 44 43 30 19 3 48 47 33 12 30 30 6 29 33 28 6 54 45 44 62 11 44 12 61 26 67 44 57 61 50 49 11 20 50 72 64 17 50 1 44 86 50 85 88 33 14 19 89 33 48 80 94 99 38 74 60 30 96...
output:
133647763790177 246961 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
result:
ok good plan!
Test #23:
score: 0
Accepted
time: 278ms
memory: 70356kb
input:
286161 1 1 2 4 4 6 6 7 9 10 10 12 12 14 15 16 16 17 18 19 21 22 22 24 24 26 27 27 28 30 30 32 33 34 35 35 36 37 39 40 40 42 42 43 45 46 46 47 49 50 50 52 52 54 55 56 56 58 59 59 61 62 62 64 65 65 67 67 69 70 70 71 73 73 75 76 76 78 78 79 80 82 82 83 85 86 86 88 88 89 90 91 93 94 95 96 97 98 98 99 10...
output:
79411033492322 95276 1 2 5 6 7 8 10 11 15 17 21 23 27 28 31 32 33 35 38 40 41 43 44 45 52 59 63 64 65 68 69 70 71 73 74 77 79 81 83 84 85 87 92 93 94 97 98 103 105 106 107 114 118 121 122 123 126 129 130 131 133 136 137 138 142 145 146 148 153 154 156 158 166 167 168 170 171 172 173 177 178 181 186 ...
result:
ok good plan!
Test #24:
score: 0
Accepted
time: 275ms
memory: 69060kb
input:
287491 1 1 3 3 4 5 6 8 8 10 11 12 13 14 14 15 16 18 18 20 21 22 23 23 24 26 27 27 29 29 31 32 32 33 34 36 37 37 39 40 40 42 43 44 44 46 47 47 48 50 50 52 53 53 55 56 56 57 58 59 61 62 63 64 65 65 66 67 68 69 70 71 72 74 74 76 76 77 78 80 80 82 83 83 85 86 87 87 89 89 90 92 92 93 94 95 96 97 98 100 1...
output:
80300962923279 96440 3 4 5 6 7 9 16 17 19 20 21 22 26 28 30 31 32 33 34 40 41 42 43 44 49 52 54 55 59 66 67 71 72 76 78 80 83 85 86 94 95 96 101 110 115 116 117 119 125 129 133 138 139 144 148 151 157 160 162 163 166 172 175 181 182 183 185 186 187 189 190 191 195 196 200 203 205 206 209 211 212 214...
result:
ok good plan!
Test #25:
score: 0
Accepted
time: 290ms
memory: 64608kb
input:
274991 1 2 2 2 3 5 7 7 8 10 11 11 13 13 15 15 17 16 18 19 19 21 22 24 24 24 26 26 28 30 31 31 31 32 33 36 35 37 37 40 39 41 43 44 43 45 47 48 47 48 49 50 53 54 54 55 57 58 57 59 60 60 61 63 63 66 65 67 69 69 69 71 73 74 75 75 77 76 79 78 80 82 82 82 83 86 85 87 87 90 90 92 92 92 94 96 95 98 98 98 99...
output:
102726959789161 136891 1 2 4 5 6 8 11 12 13 15 16 18 19 21 24 25 28 29 31 33 35 36 38 39 40 42 43 48 49 55 59 60 64 66 69 70 71 73 74 80 81 83 86 90 91 93 94 98 100 101 102 104 105 107 108 109 110 113 114 116 119 120 121 122 124 128 129 130 133 136 138 143 145 147 148 149 154 155 157 159 160 162 165...
result:
ok good plan!
Test #26:
score: 0
Accepted
time: 412ms
memory: 66156kb
input:
299745 1 1 2 2 3 4 6 8 7 9 11 12 12 14 14 15 17 17 18 18 20 22 22 24 24 26 27 27 28 29 31 31 32 34 35 34 35 36 39 38 39 41 42 44 45 46 47 48 47 48 50 51 52 52 55 54 56 57 58 59 61 60 63 64 64 65 66 68 69 70 69 71 72 74 73 76 77 78 77 78 81 80 81 84 85 85 86 86 88 90 91 92 91 94 94 96 96 97 99 99 101...
output:
112117667496638 149530 1 2 3 4 5 6 7 9 10 11 13 15 16 17 18 19 20 21 22 23 24 26 28 31 32 34 35 37 39 42 43 44 45 47 48 49 53 54 56 61 62 65 78 80 82 84 86 88 91 94 95 98 99 101 104 106 108 109 111 112 113 115 117 118 120 121 122 124 127 128 133 134 135 136 137 143 145 146 147 149 150 151 152 156 16...
result:
ok good plan!
Test #27:
score: 0
Accepted
time: 532ms
memory: 53980kb
input:
292442 1 1 1 4 1 3 6 1 1 7 2 11 10 12 6 12 16 11 17 18 19 15 15 22 25 21 24 25 27 27 29 31 32 30 34 28 36 33 31 32 36 35 41 41 43 37 41 46 45 45 49 45 49 54 51 50 52 54 58 58 56 54 61 64 64 63 58 64 61 67 69 66 64 74 68 76 75 73 78 76 77 80 80 83 77 79 86 86 86 86 82 89 85 87 92 95 97 92 99 93 93 94...
output:
133601484858390 208943 1 2 3 4 5 6 7 8 9 10 11 12 14 15 17 18 19 20 21 23 24 25 26 27 28 29 31 32 34 35 37 38 39 40 41 42 45 46 47 48 49 50 51 52 53 54 55 57 58 60 61 62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 81 83 84 86 88 89 90 91 92 93 94 97 98 99 102 103 105 106 107 108 109 110 112 113 ...
result:
ok good plan!
Test #28:
score: 0
Accepted
time: 517ms
memory: 55392kb
input:
288885 1 1 1 1 5 1 2 1 4 4 7 5 12 11 8 12 16 12 10 17 13 14 23 15 19 17 20 24 20 25 27 25 33 32 35 27 33 36 39 38 39 42 43 36 40 41 42 39 41 43 44 43 47 50 48 50 53 54 57 54 57 54 54 57 59 58 67 60 65 67 69 70 73 67 72 70 69 77 73 72 79 75 78 84 78 82 87 85 88 81 91 91 84 92 87 89 93 95 92 99 93 94 ...
output:
132411383976016 206725 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 39 40 41 47 50 52 53 54 55 56 57 59 60 61 62 64 65 66 68 69 70 72 74 77 79 82 83 84 85 86 87 88 89 90 91 93 96 98 101 102 105 106 108 109 110 111 115 118 119 121 122 123 124 125 127 12...
result:
ok good plan!
Test #29:
score: 0
Accepted
time: 507ms
memory: 54612kb
input:
292428 1 1 1 4 3 4 5 5 2 9 6 12 12 6 15 8 11 13 16 13 13 16 17 17 19 24 26 26 28 28 28 24 27 31 30 36 37 29 30 34 40 38 36 44 43 43 40 39 43 48 50 46 48 46 53 51 55 51 50 58 57 57 58 55 62 57 64 59 63 65 65 64 66 65 68 75 68 76 72 73 74 82 75 77 83 82 82 79 82 87 91 90 90 87 95 96 96 95 90 91 98 94 ...
output:
133851024092098 208716 1 2 4 6 7 9 10 11 12 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 37 38 39 40 41 44 45 47 48 49 50 51 52 53 55 56 57 58 59 61 63 64 65 66 69 70 71 72 73 75 77 78 79 81 82 83 85 86 87 89 90 91 92 94 95 96 97 98 99 100 101 102 103 105 106 107 108 110 111 112 113 114 ...
result:
ok good plan!
Test #30:
score: 0
Accepted
time: 819ms
memory: 49044kb
input:
287464 1 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 13 1 1 1 1 1 1 1 1 1 1 1 22 31 1 32 1 1 1 4 1 1 1 1 1 1 1 1 1 37 1 21 27 9 11 1 38 7 1 52 5 1 36 39 1 55 35 62 65 44 50 1 1 1 54 1 20 44 72 44 1 63 70 65 1 28 1 36 2 77 25 1 2 81 35 22 53 96 72 16 78 81 68 89 34 71 16 36 26 49 71 23 57 106 33 59 71 22 65 55...
output:
134208193305014 217618 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
result:
ok good plan!
Test #31:
score: 0
Accepted
time: 728ms
memory: 48628kb
input:
286884 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 1 1 1 1 1 1 1 1 1 8 21 1 23 5 1 1 2 1 1 1 17 1 20 19 38 14 16 24 14 1 10 32 1 22 1 42 1 1 1 1 61 2 61 1 35 41 56 1 1 7 43 1 69 1 34 36 1 53 75 30 63 44 2 1 71 77 43 56 21 26 10 1 33 78 47 26 44 98 10 41 99 61 73 57 69 9 45 85 40 20 44 15 42 47 97 112 7...
output:
133652038928902 216742 1 2 4 5 6 7 8 10 11 12 13 14 15 16 18 19 20 22 23 24 26 27 28 29 30 33 34 35 36 38 39 40 41 43 44 45 46 47 48 49 50 51 53 54 55 58 59 60 61 62 64 65 68 69 70 71 72 74 75 76 77 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98 99 101 102 103 105 106 107 110 111 112 11...
result:
ok good plan!
Test #32:
score: 0
Accepted
time: 739ms
memory: 49860kb
input:
281442 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 8 1 1 1 2 1 1 1 1 1 1 1 1 5 13 13 1 28 1 1 1 1 24 1 1 6 1 1 1 1 16 19 14 43 1 9 21 1 1 1 15 22 1 15 8 48 53 1 20 1 1 31 1 72 57 19 1 67 1 14 54 1 35 23 38 70 1 41 64 52 62 13 14 60 84 55 23 70 58 1 32 21 7 84 21 50 31 103 87 73 107 99 16 43 105 31 105 109...
output:
131262917382920 212420 2 3 4 5 6 7 8 9 11 12 13 14 15 16 18 20 21 22 23 24 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 82 83 84 87 88 89 90 91 92 93 94 96 97 98 99 100 101 102 103 104 105 ...
result:
ok good plan!
Test #33:
score: 0
Accepted
time: 817ms
memory: 48532kb
input:
284225 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 28 1 24 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 54 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 74 50 1 1 1 62 1 106 84 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
132547083915792 215443 1 2 3 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 65 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...
result:
ok good plan!
Test #34:
score: 0
Accepted
time: 858ms
memory: 48448kb
input:
291112 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 38 1 1 1 1 38 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 61 1 1 1 1 1 1 1 1 1 1 1 1 1 1 70 1 1 1 1 1 59 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 78 1 1 1 1 1 1 1 1 1 1 1 20 1 1 1 1 36 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11...
output:
136147527273630 221269 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 53 54 55 56 57 58 61 63 64 65 66 67 68 69 70 72 73 74 75 76 78 79 80 81 82 83 84 85 87 88 89 90 91 92 93 94 95 96 98 99 100 101 102 103 ...
result:
ok good plan!