QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#940928 | #10163. Tree Quiz | volfrid | AC ✓ | 310ms | 114888kb | C++20 | 4.5kb | 2025-03-18 06:34:19 | 2025-03-18 06:34:19 |
Judging History
answer
#include <iostream>
#include <vector>
#include <functional>
#include <cstdint>
#include <cmath>
#define dbg(x) std::cerr << #x << " = " << x << "\n";
using Graph = std::vector<std::vector<int>>;
using i64 = std::int64_t;
struct Node {
int l = 0, r = 0;
int sum = 0;
};
struct PersistentSegmentTree {
PersistentSegmentTree(const int N, const int nodes_count) : N(N) {
T.reserve(nodes_count);
T.emplace_back();
}
[[nodiscard]] int add(const int u, const int l, const int r, const int pos, const int value) {
auto idx = this->new_();
T[idx] = T[u];
if (l == r) {
T[idx].sum += value;
} else {
const auto m = (l + r) / 2;
if (pos <= m) {
T[idx].l = add(T[idx].l, l, m, pos, value);
} else {
T[idx].r = add(T[idx].r, m + 1, r, pos, value);
}
this->pull(idx);
}
return idx;
}
[[nodiscard]] int add(const int u, const int pos, const int value) {
return this->add(u, 0, N - 1, pos, value);
}
[[nodiscard]] int join(const int x, const int y, const int l, const int r) {
if (x == 0 || y == 0) {
return x + y;
}
auto idx = this->new_();
if (l == r) {
T[idx].sum = T[x].sum + T[y].sum;
} else {
const int m = (l + r) / 2;
T[idx].l = join(T[x].l, T[y].l, l, m);
T[idx].r = join(T[x].r, T[y].r, m + 1, r);
}
this->pull(idx);
return idx;
}
[[nodiscard]] int join(const int x, const int y) {
return this->join(x, y, 0, N - 1);
}
// query function somewhere in here
std::pair<int, int> query(const int lhs, const int rhs, const int l, const int r, const int k) {
if (l == r) {
return {l, k};
}
const auto sum = T[T[lhs].l].sum - T[T[rhs].l].sum;
const auto m = (l + r) / 2;
if (sum >= k) {
return query(T[lhs].l, T[rhs].l, l, m, k);
} else {
return query(T[lhs].r, T[rhs].r, m + 1, r, k - sum);
}
}
std::pair<int, int> query(const int lhs, const int rhs, const int k) {
return this->query(lhs, rhs, 0, N - 1, k);
}
std::pair<int, int> query(const int root, const int k) {
return this->query(root, 0, k);
}
int new_() {
T.emplace_back();
return T.size() - 1;
}
void pull(const int idx) {
T[idx].sum = T[T[idx].l].sum + T[T[idx].r].sum;
}
int N;
std::vector<Node> T;
};
int main() {
int N, Q;
std::cin >> N >> Q;
Graph G(N);
int root = 0;
std::vector<int> parent(N + 1, N);
for (int i = 0; i < N; i++) {
std::cin >> parent[i];
parent[i]--;
if (parent[i] == -1) {
root = i;
} else {
G[parent[i]].push_back(i);
}
}
const int max_nodes = std::ceil(1 + std::log2(N)) * N * 2;
PersistentSegmentTree DS_lca{N, max_nodes}, DS_values{N, max_nodes};
std::vector<int> root_lca(N), root_values(N);
std::vector<int> subtree_size(N), depth(N);
std::vector<std::vector<int>> up(std::ceil(2 + std::log2(N)), std::vector<int>(N + 1, N));
parent[root] = N;
std::function<void(const int)> dfs = [&](const int u) -> void {
up[0][u] = parent[u];
for (int l = 1; (1 << l) <= N; l++) {
up[l][u] = up[l - 1][up[l - 1][u]];
}
subtree_size[u] = 1;
for (const int v : G[u]) {
depth[v] = depth[u] + 1;
dfs(v);
subtree_size[u] += subtree_size[v];
}
};
dfs(root);
std::function<void(const int)> dfs_build = [&](const int u) -> void {
root_lca[u] = DS_lca.add(root_lca[u], u, subtree_size[u]);
root_values[u] = DS_values.add(root_values[u], u, 1);
for (const int v : G[u]) {
root_lca[v] = root_lca[u];
root_lca[v] = DS_lca.add(root_lca[v], u, -subtree_size[v]);
dfs_build(v);
root_values[u] = DS_values.join(root_values[u], root_values[v]);
}
};
root_lca[root] = DS_lca.new_();
dfs_build(root);
auto jump_up = [&](int u, const int delta) -> int {
for (int i = up.size() - 1; i >= 0; i--) {
if ((delta & (1 << i)) > 0) {
u = up[i][u];
}
}
return u;
};
for (int i = 0; i < Q; i++) {
i64 k;
std::cin >> k;
int x = (k - 1) / N;
const int rest = (k - 1) % N + 1;
const auto [lca, new_rest] = DS_lca.query(root_lca[x], rest);
int l_bellow = 0;
if (lca != x) {
l_bellow = root_values[jump_up(x, depth[x] - depth[lca] - 1)];
}
const auto [y, _] = DS_values.query(root_values[lca], l_bellow, new_rest);
std::cout << (i64)N * N * x + (i64)N * lca + y << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
5 3 3 0 2 2 3 1 18 25
output:
0 82 124
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1 1 0 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
300 1000 0 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 1...
output:
5327916 21581976 15622083 20912508 10655561 19305451 24756321 15227458 7856250 25059130 5237526 22843745 20700602 18146588 21919966 19685642 25804715 1896478 296 1715722 15221438 12333311 10655625 10441505 20113645 4063673 25229197 10384687 4154043 8939986 10375284 3341178 14941505 4876355 26400100 ...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
300 1000 0 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 1...
output:
0 90000 180000 270602 360903 450301 541505 631204 721806 811806 900301 990903 1083010 1172408 1261806 1351806 1444515 1534214 1620000 1715117 1804816 1895117 1983913 2074515 2163612 2253311 2342408 2432709 2527826 2613010 2702408 2799331 2880903 2973311 3064515 3157224 3245719 3330903 3426923 351571...
result:
ok 1000 lines
Test #5:
score: 0
Accepted
time: 42ms
memory: 4096kb
input:
300 90000 0 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 ...
output:
0 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 101 10...
result:
ok 90000 lines
Test #6:
score: 0
Accepted
time: 55ms
memory: 4096kb
input:
300 100000 0 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...
output:
8849603 25193988 18101739 2799509 18313043 4597525 10565335 24914046 24981170 3966622 25912474 22623712 22512642 14990029 7946643 3792824 18042441 5327992 5056925 17496722 3070414 8759302 11378001 2794816 1535290 3250913 9752683 1354722 7766012 19103177 17058160 18396120 5147304 7402575 15883344 121...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 113ms
memory: 77520kb
input:
78389 5 33487 77089 27981 73896 46472 48234 35441 73809 65081 62732 27144 41190 22052 6601 54521 25538 12849 25139 7955 2888 560 65683 62389 20227 26954 26555 61996 34967 41099 4061 7469 29054 25664 59634 27743 75654 60836 39672 29424 68875 2276 37485 42956 67749 33929 78069 51457 46619 63053 41620 ...
output:
327753830297976 328878335134962 335576205649839 255920705404580 179116408732653
result:
ok 5 lines
Test #8:
score: 0
Accepted
time: 127ms
memory: 87196kb
input:
89272 2 32030 60254 73018 74707 67667 86264 75261 45862 64043 64540 79879 65832 62630 2067 13631 65096 49308 11346 7834 56048 14150 16979 3374 55707 47414 10398 71283 68711 78891 65285 62794 21759 74768 3046 67938 2947 81772 28664 47917 85910 59506 33994 62481 35920 28052 73386 39658 79301 21612 592...
output:
542941973345600 85461370277361
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 145ms
memory: 99272kb
input:
100000 5 27675 69722 55195 80299 45710 21002 41942 77009 19110 31701 53866 78774 21515 57725 27216 19418 54890 30039 22354 8739 53058 49967 6697 20426 53425 91335 37529 49532 60119 18191 87128 23250 8644 83001 48285 1047 2152 5845 22306 14386 12581 52946 59454 23242 80992 43593 84069 91861 39630 118...
output:
737395068445482 832495068447852 199585068418439 557998894524177 132248183586103
result:
ok 5 lines
Test #10:
score: 0
Accepted
time: 84ms
memory: 107852kb
input:
100000 5 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:
96555000086541 333603336014372 632375000014756 212363721937219 534215000018873
result:
ok 5 lines
Test #11:
score: 0
Accepted
time: 38ms
memory: 3968kb
input:
300 90000 0 286 46 288 233 294 121 293 13 244 219 84 27 1 7 156 235 71 227 245 37 282 18 147 53 172 300 174 156 252 27 62 246 121 296 25 5 136 164 224 17 58 56 11 217 248 82 40 36 242 84 114 205 113 210 255 90 256 195 275 147 289 277 244 121 131 104 64 49 179 70 293 169 220 1 263 188 273 194 200 118...
output:
0 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 101 10...
result:
ok 90000 lines
Test #12:
score: 0
Accepted
time: 39ms
memory: 4096kb
input:
300 90000 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 ...
output:
0 301 602 903 1204 1505 1806 2107 2408 2709 3010 3311 3612 3913 4214 4515 4816 5117 5418 5719 6020 6321 6622 6923 7224 7525 7826 8127 8428 8729 9030 9331 9632 9933 10234 10535 10836 11137 11438 11739 12040 12341 12642 12943 13244 13545 13846 14147 14448 14749 15050 15351 15652 15953 16254 16555 1685...
result:
ok 90000 lines
Test #13:
score: 0
Accepted
time: 28ms
memory: 3584kb
input:
1 100000 0 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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 64ms
memory: 4864kb
input:
2073 100000 832 1970 962 1383 640 2021 819 739 596 1353 1226 127 1042 1115 1777 1057 1825 874 1458 679 23 1034 1060 1744 1749 1703 827 1491 242 2024 97 1152 1715 1845 1917 385 500 629 743 73 233 418 266 584 1060 629 84 138 1068 753 1002 1729 923 426 1159 1172 98 319 1632 544 364 1049 1876 664 1278 5...
output:
2473356457 7510320544 1148410040 3902998685 2751314092 8851086691 8630059007 3593589531 7671755423 3030640433 1360349742 3980350105 8552707085 5717840191 2880232970 4474542490 5168277103 293240443 2549339400 6901806956 6538631089 2880233642 138537609 4397191056 886273738 6006254262 4689409979 834213...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 67ms
memory: 4608kb
input:
2179 100000 569 1483 1534 514 351 656 1960 1076 1227 1116 2151 570 2134 1369 2113 1864 914 2118 1098 1779 2167 1672 2145 857 717 1228 1130 118 967 1125 232 935 1193 840 1671 2146 1878 281 1864 935 124 163 363 1825 408 448 1340 1702 1568 387 807 525 1847 932 2156 1991 1534 1543 2123 1416 1736 996 39 ...
output:
4445295736 9212328302 9896047768 5290447913 2180480946 4886864660 3395978463 5902944658 5129013649 4611760743 983975082 409462282 9359518446 3676112917 4017972425 6501197132 5902944221 1591724270 7868632887 6619622342 10242654712 3942004046 1867109450 4877091988 4682698250 3642877949 281265272 58839...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 54ms
memory: 5120kb
input:
2500 100000 2111 1970 613 2248 1245 829 509 618 448 2127 223 222 326 1845 907 395 238 113 661 2113 1492 1026 1065 2217 1207 1030 2277 468 85 1685 482 1394 1395 1915 466 1988 392 1068 559 381 675 578 1974 278 1028 1200 1509 1129 1663 1199 1936 2017 1018 600 2382 1194 372 1933 108 2226 1569 352 975 17...
output:
11233685873 5346186250 14977436279 139935974 977436448 5079972252 10877437406 9877437458 8477435576 6239935409 15564936573 8889935619 15246185245 5758685307 9039936022 15121185300 3477436418 9073537108 9896186418 12471187384 8639935750 7914935889 14133686886 15083686556 14534015002 6814936920 128086...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 79ms
memory: 5376kb
input:
2500 100000 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 10...
output:
10584621348 13472413965 3978126613 13372714085 1090626988 2659376552 7815626064 832578031 2828127419 12921875183 10921875281 1577288415 1676983293 9290916366 5353126652 13367101840 2358963585 12109375133 10079032180 6365626753 3209376427 2395065526 6090626653 3965626930 6165627304 6752700626 1320345...
result:
ok 100000 lines
Test #18:
score: 0
Accepted
time: 58ms
memory: 3968kb
input:
708 100000 0 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...
output:
68268538 174022270 260476484 125454964 120806751 312673168 46181660 121979781 221226166 185503839 171173032 278093057 328026594 259520126 253761532 320957141 107422243 95877093 201184114 20079172 261528009 208309578 124442510 115370837 353540719 147482929 201291364 153101818 18573541 292796314 21233...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 60ms
memory: 3940kb
input:
582 100000 0 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...
output:
109573424 182442226 95006172 58292593 11876236 74951867 46824750 88559204 173645313 112310867 170527420 73968956 57003622 14251173 93648756 9161348 57343136 71197919 72604119 92631110 82790949 157027432 136509853 85844930 93159594 49199924 145902062 182416574 125449727 161244867 107159797 22055435 6...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 68ms
memory: 5504kb
input:
2500 100000 0 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 9...
output:
5577231025 168819786 1744449620 5070779744 2507253973 4014107417 10920663265 2438476111 10387987695 7790616882 14676933273 1144208955 13749249933 4245448686 2788130252 11419130152 9972739287 12121891256 1882004227 9152993697 10702420968 11765933873 12048061724 6852741361 8538612945 350141586 6233743...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 289ms
memory: 99244kb
input:
100000 100000 0 1 2 2 2 3 2 7 6 3 2 7 1 5 6 13 13 1 13 18 9 4 3 9 3 21 12 15 10 23 22 4 9 7 34 19 8 29 38 4 2 35 40 15 32 22 20 12 47 40 3 21 17 4 41 54 34 19 52 40 22 39 39 48 51 37 20 11 61 10 69 64 3 53 66 58 29 43 34 10 26 49 72 71 83 14 72 70 44 17 76 38 55 6 12 47 6 23 70 4 56 41 43 46 92 18 6...
output:
986070000179396 492340096911422 303520000074342 797410000072372 433100000118856 356010000039327 517370000119116 210810000071160 627830000247183 659030000144681 460850000168510 793200000047403 734670000238718 988950000078617 493460000183748 396320000086509 885910000137731 843760000280561 772130000103...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 301ms
memory: 99264kb
input:
100000 100000 0 1 1 2 1 5 5 4 5 8 10 9 4 3 14 11 5 3 9 17 18 16 19 18 7 8 6 13 3 3 24 6 2 2 14 17 25 36 13 2 38 7 39 16 1 44 22 5 9 26 42 34 43 9 10 15 31 51 48 27 32 9 50 9 56 11 3 25 46 50 18 62 12 31 55 29 8 46 16 79 29 55 6 37 62 21 7 36 7 75 46 70 10 22 79 22 1 34 8 20 75 81 58 45 34 43 83 80 7...
output:
668070000012365 67730000483506 743540000011350 603150000047610 549350000058528 402230001384886 642680000482786 621500000030266 650810000038840 98060000335634 263450000027968 601710000000962 507370000330570 975120000081315 999470000072123 273670000027172 933170000007120 453530000096371 92400000471956...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 310ms
memory: 109024kb
input:
100000 100000 0 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...
output:
730993778455059 497144971450450 173961739683823 337253372583836 830565545455454 364711871186527 684100827308273 81260812618822 548822019889630 238322383226753 300940021079212 152501525093297 529550241302413 868084675982979 607683328484986 507854180241802 648444273271337 323323233283004 9685331925770...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 146ms
memory: 98420kb
input:
100000 100000 0 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:
0 10000000000 20000000000 30000000000 40000000000 50000000000 60000000000 70000000000 80000000000 90000000000 100000000000 110000000000 120000000000 130000000000 140000000000 150000000000 160000000000 170000000000 180000000000 190000000000 200000000000 210000000000 220000000000 230000000000 24000000...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 242ms
memory: 72860kb
input:
73833 100000 8431 69701 40277 61730 13590 69377 40722 8407 408 18996 22602 34602 61242 51292 34555 1285 31780 20879 7777 28091 64913 56889 42826 10459 35408 33573 8256 68996 4979 31117 5949 40457 15241 44609 7514 25154 38357 21064 34480 42874 67193 22339 65981 61173 53924 12698 54960 24701 8163 4801...
output:
160517072750124 212782861446427 6630599762251 326689413053377 361070837164955 74081071486500 301166370783292 229296274855925 225796230073177 233875376880191 304284521185146 260614061660965 163918691359171 178811675495487 239615608293908 83534452530030 176200497064051 109165714798692 202437661171238 ...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 171ms
memory: 42324kb
input:
43956 100000 26202 39174 37007 4677 14241 34149 42008 11821 8619 27454 7175 39248 19087 22731 27928 7350 9923 30873 26847 35565 25374 24253 13216 30162 43221 23688 37036 1370 43774 20025 12026 12583 10594 17822 3590 43198 7523 6345 15628 21833 41390 27701 18336 26734 8715 18562 21901 18883 11935 307...
output:
6636151170599 43905439460095 25112920739660 70431669926807 14134972967086 13891026402808 66299378575324 29672747405721 21597085792361 20961188035221 494364028041 48786018256460 30693553559882 65959996032786 38342855986344 74490433402530 59189896421618 79011617454663 10121524588762 26178165906897 807...
result:
ok 100000 lines
Test #27:
score: 0
Accepted
time: 278ms
memory: 99260kb
input:
100000 100000 70055 55618 94565 83769 73623 5096 22162 89981 93964 48846 7488 82440 5700 45126 36278 63360 6088 51317 81136 87634 86943 27607 45494 56948 69588 87252 21050 20154 62076 47647 92496 3788 33944 17980 96965 43746 82198 17896 73241 66164 39010 81126 67039 8956 61497 89492 60451 61521 5019...
output:
670550764716726 108532846478425 431502846463728 597000764730883 568231178544842 49160764792803 96560764766158 254752846412647 189290764720557 611210764780997 971190764724091 927374606418009 909979823399034 589052846422525 828009823356578 556462846442324 545136875819453 524190764758014 50739076472306...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 241ms
memory: 107856kb
input:
100000 100000 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 ...
output:
824025000042852 394265000098183 564845648487907 507705077055509 963867215372153 951465000044644 440385000078481 727235000041970 433884338804989 420925000070234 837345342653426 806395701157011 314205000082821 662535358353583 624896248995053 10795000066591 644765882258822 186291862915251 1526131149311...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 72ms
memory: 5376kb
input:
2500 100000 0 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 9...
output:
2438476020 8945685774 9789134937 13402378451 1162967276 11876190476 12301450580 4701881156 13100604169 3226291257 1469339154 6989965986 13163475390 10613022185 4107894049 8901918267 10458700980 3119998455 4789283213 8672073829 9401579258 14519788207 14258313325 1818932573 14020790816 2057073800 7108...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 45ms
memory: 4096kb
input:
300 90000 0 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 ...
output:
0 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 101 10...
result:
ok 90000 lines
Test #31:
score: 0
Accepted
time: 114ms
memory: 109060kb
input:
100000 5 0 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 1...
output:
158841588420207 185321455014550 823911825962554 24700247088316 853221915123477
result:
ok 5 lines
Test #32:
score: 0
Accepted
time: 211ms
memory: 98500kb
input:
100000 100000 0 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:
548810000039251 844260000072433 544880000023084 623560000023968 437580000039023 56710000001546 383440000030358 812160000038982 568040000052578 836070000028209 87120000000176 368240000035247 778150000067700 870080000041208 799150000036879 520470000035334 118270000007568 582010000031276 94466000004929...
result:
ok 100000 lines
Test #33:
score: 0
Accepted
time: 213ms
memory: 98500kb
input:
100000 100000 0 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:
932340000062349 827090000007925 505740000021848 205090000055212 854270000065769 488830000098178 259900000022726 282160000079108 456030000063664 399050000098247 50950000014444 8810000061713 820320000063194 724660000085464 709360000023248 662950000062914 133400000073639 919270000080308 210400000057041...
result:
ok 100000 lines
Test #34:
score: 0
Accepted
time: 46ms
memory: 3840kb
input:
300 90000 0 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:
0 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 101 10...
result:
ok 90000 lines
Test #35:
score: 0
Accepted
time: 43ms
memory: 3968kb
input:
300 100000 0 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:
8460115 15660184 6570165 12780072 22590162 10980177 25470214 13410161 6840241 13860171 4770178 20700144 7650220 4230129 16200089 2250054 11610251 19710155 5310147 8370128 25650120 16740021 12330148 6120026 2790152 22500078 18450057 25200125 24660288 18270255 4050017 5670236 15930168 13320014 9090124...
result:
ok 100000 lines
Test #36:
score: 0
Accepted
time: 268ms
memory: 114888kb
input:
100000 100000 0 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...
output:
260352603539847 894388943899899 873765160451604 435394353968550 321763217650084 924984691346913 253782537849124 237640646006460 220682206830537 322253222542120 582982846328463 500443446434464 829571543715437 858334507045070 894011489014890 654850487404874 984601036210362 49260492655307 5113412711127...
result:
ok 100000 lines
Test #37:
score: 0
Accepted
time: 244ms
memory: 114888kb
input:
100000 100000 0 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...
output:
0 10000000000 20000000000 30000100001 40000100001 50000400004 60000500005 70000200002 80000000000 90000700007 100000000000 110000800008 120000500005 130000700007 140000500005 150000800008 160000900009 170001500015 180000900009 190001900019 200000800008 210000200002 220000300003 230001400014 24000210...
result:
ok 100000 lines