QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670039 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | KellyWLJ | 100 ✓ | 695ms | 122000kb | C++17 | 7.2kb | 2024-10-23 20:18:35 | 2024-10-23 20:18:35 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
using pii = pair<int, int>;
const int N = 200010, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
if(bgn == til) bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
char ch = getc(); T fh = 0; x = 0;
while(ch < '0' || ch > '9') fh |= (ch == '-'), ch = getc();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getc();
x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args) {read(x), read(args...);}
template<typename T>
void print(T x) {
if(x < 0) putchar('-'), x = -x;
if(x / 10) print(x / 10);
putchar(x % 10 + '0');
}
int n, q, u[N], v[N], d[N], fa[N], ans[N];
vector<int> edge[N];
struct clpf {
vector<pii> ask[N]; // f
int mson[N], top[N], dfn[N], cnt, dep[N], f[N];
void dfs(int x) {
for(int y : edge[x]) if(y != fa[x]) {
dfs(y), dep[x] = max(dep[y] + 1, dep[x]);
if(!mson[x] || dep[y] > dep[mson[x]]) mson[x] = y;
}
}
void dfs2(int x, int tp) {
top[x] = tp, dfn[x] = ++cnt;
if(mson[x]) dfs2(mson[x], tp);
for(int y : edge[x]) if(y != fa[x] && y != mson[x]) dfs2(y, y);
}
void Dfs(int x) {
if(mson[x]) Dfs(mson[x]), f[dfn[x]] = f[dfn[x] + 1] + 1;
else f[dfn[x]] = 1;
for(int y : edge[x]) if(y != fa[x] && y != mson[x]) {
Dfs(y), f[dfn[x]] += f[dfn[y]];
for(int i = dep[y]; i >= 0; --i) f[dfn[x] + i + 1] += f[dfn[y] + i];
}
// cerr << x << " : " << dfn[x] << " " << f[dfn[x]] << " " << mson[x] << "\n";
for(auto [d, i] : ask[x]) {
int tmp = f[dfn[x]] - (d + 1 <= dep[x] ? f[dfn[x] + d + 1] : 0);
// cerr << "2 : " << x << " " << d << " " << tmp << " " << i << "\n";
i > 0 ? ans[i] += tmp : ans[-i] -= tmp;
}
}
void work() {
dfs(1), dfs2(1, 1), Dfs(1);
// for(int i = 1; i <= n; ++i) cerr << dep[i] << " ";
// cerr << "\n";
}
}tr2;
struct dfz {
vector<pii> ask[N]; // x's neighbours
int siz[N], vis[N], dep[N], root, tot, mn, mx, buc[N], nmx, tmp[N];
void dfszx(int x, int fa) {
siz[x] = 1;
int res = 0;
for(int y : edge[x]) if(y != fa && !vis[y])
dfszx(y, x), siz[x] += siz[y], res = max(res, siz[y]);
res = max(res, tot - siz[x]);
if(res < mn) mn = res, root = x;
}
void getroot(int x) {dfszx(x, 0), tot = siz[x], mn = N, dfszx(x, 0);}
void add(int x, int fa, int op) {
dep[x] = dep[fa] + 1, mx = max(mx, dep[x]), buc[dep[x]] += op;
for(int y : edge[x]) if(y != fa && !vis[y]) add(y, x, op);
}
void dfs(int x, int fa, int op) {
tmp[dep[x]] += op, nmx = max(nmx, dep[x]);
for(int y : edge[x]) if(y != fa && !vis[y]) dfs(y, x, op);
}
void calc(int x, int fa) {
for(auto [d, i] : ask[x]) {
int ndep = d - (dep[x] - dep[root]), nw = ndep >= 0 ? buc[min(mx, dep[root] + ndep)] - tmp[min(nmx, dep[root] + ndep)] : 0;
i > 0 ? ans[i] += nw : ans[-i] -= nw;
}
for(int y : edge[x]) if(y != fa && !vis[y]) calc(y, x);
}
void solve(int x) {
vis[x] = 1, mx = 0, root = x, add(x, 0, 1);
for(int i = dep[x] + 1; i <= mx; ++i) buc[i] += buc[i - 1];
for(auto [d, i] : ask[x]) i > 0 ? ans[i] += buc[min(mx, dep[x] + d)] : ans[-i] -= buc[min(mx, dep[x] + d)];
for(int y : edge[x]) if(!vis[y]) {
nmx = 0, dfs(y, x, 1);
for(int i = dep[x] + 2; i <= nmx; ++i) tmp[i] += tmp[i - 1];
calc(y, x);
for(int i = dep[x]; i <= nmx; ++i) tmp[i] = 0;
}
for(int i = dep[x]; i <= mx; ++i) buc[i] = 0;
for(int y : edge[x]) if(!vis[y]) getroot(y), solve(root);
}
void work() {
getroot(1), solve(root);
}
}tr3;
struct zlpf {
vector<pii> ask[N]; // g 1~x
int siz[N], mson[N], top[N], dep[N], dfn[N], mxdfn[N], cnt, ord[N], buc[N];
void dfs(int x, int fath) {
siz[x] = 1, fa[x] = fath, dep[x] = dep[fath] + 1;
for(int y : edge[x])
if(y != fath) {
dfs(y, x), siz[x] += siz[y];
if(siz[y] > siz[mson[x]]) mson[x] = y;
}
}
void dfs2(int x, int tp) {
top[x] = tp, dfn[x] = ++cnt, ord[cnt] = x;
if(mson[x]) dfs2(mson[x], tp);
for(int y : edge[x]) if(y != fa[x] && y != mson[x]) dfs2(y, y);
mxdfn[x] = cnt;
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dfn[x] < dfn[y] ? x : y;
}
int jump(int x, int y) {
int las = x;
while(top[x] != top[y]) las = top[x], x = fa[top[x]];
return x == y ? las : mson[y];
}
void work() {dfs(1, 0), dfs2(1, 1);}
void solve(int x, int y, int id, int op = 1) {
int las = 0;
ask[x].pb({d[id], id}), ask[fa[y]].pb({d[id], -id});
while(top[x] != top[y]) {
tr2.ask[mson[x]].pb({d[id] - 1, id}), tr2.ask[las].pb({d[id] - 1, -id});
las = top[x], x = fa[top[x]];
}
tr2.ask[mson[x]].pb({d[id] - 1, id}), tr2.ask[las].pb({d[id] - 1, -id});
if(op) tr3.ask[y].pb({d[id], id}), tr2.ask[y].pb({d[id], -id});
}
void dfs3(int x, int sum) {
auto calc = [&](int op) -> void {
buc[0] += op * siz[x], sum += op;
for(int y : edge[x]) if(y != fa[x] && y != mson[x]) {
for(int i = dfn[y]; i <= mxdfn[y]; ++i) buc[dep[ord[i]] - dep[x]] += siz[ord[i]] * op;
sum += siz[y] * op;
}
};
calc(1);
for(auto [d, i] : ask[x]) {
int tmp = sum - buc[d + 1];
i > 0 ? ans[i] += tmp : ans[-i] -= tmp;
}
for(int y : edge[x]) if(y != fa[x]) dfs3(y, sum);
calc(-1);
}
}tr1;
int main() {
#ifdef Kelly
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
#endif
read(n);
for(int i = 1, u, v; i < n; ++i) read(u, v), edge[u].pb(v), edge[v].pb(u);
tr1.work();
read(q);
for(int i = 1; i <= q; ++i) {
read(u[i], v[i], d[i]);
if(tr1.dfn[u[i]] > tr1.dfn[v[i]]) swap(u[i], v[i]);
int lca = tr1.lca(u[i], v[i]);
if(d[i] == 0) {ans[i] = tr1.dep[u[i]] + tr1.dep[v[i]] - tr1.dep[lca] * 2 + 1; continue;}
if(lca == u[i]) tr1.solve(v[i], u[i], i);
else {
int x = tr1.jump(u[i], lca), y = tr1.jump(v[i], lca);
tr1.solve(u[i], x, i, 0), tr1.solve(v[i], y, i, 0);
tr3.ask[lca].pb({d[i], i}), tr2.ask[x].pb({d[i] - 1, -i}), tr2.ask[y].pb({d[i] - 1, -i});
}
}
tr1.dfs3(1, 0), tr2.work(), tr3.work();
for(int i = 1; i <= q; ++i) print(ans[i]), putchar('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 8ms
memory: 31976kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
ok 4966 numbers
Test #2:
score: 7
Accepted
time: 8ms
memory: 34028kb
input:
4914 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 ...
output:
3378 4914 231 4914 4914 3378 22 4914 4914 2559 4914 75 219 1407 1138 863 24 3890 4914 4914 399 399 13 139 77 4914 4095 3071 4914 23 151 110 1407 43 54 4914 4914 1919 2559 77 735 3071 24 133 479 4914 33 831 4 4914 4914 79 4914 199 3890 3071 73 567 15 75 21 126 4914 4914 203 4914 75 127 62 41 4914 409...
result:
ok 4975 numbers
Test #3:
score: 7
Accepted
time: 3ms
memory: 33660kb
input:
4921 1151 2767 2767 322 322 4451 4451 4867 4867 1265 1265 3197 3197 3890 3890 1052 1052 1407 1407 1578 1578 566 566 2965 2965 260 260 4908 4908 308 308 553 553 2845 2845 4249 4249 1284 1284 73 73 1088 1088 277 277 1878 1878 4128 4128 3609 3609 2126 2126 149 149 3467 3467 1653 1653 4913 4913 3604 360...
output:
4921 3192 3260 3983 949 2080 605 3471 4901 2020 2552 1570 3325 3643 458 1296 3072 3423 3045 2569 1720 3195 1908 4397 1536 2799 3072 2443 3176 3311 1403 1119 842 3028 2387 1903 2303 4921 2149 1974 4153 2053 2888 2344 3264 3709 3443 3601 2571 1207 4519 3745 959 1920 1305 1706 1743 522 1266 2153 1812 1...
result:
ok 4930 numbers
Test #4:
score: 7
Accepted
time: 8ms
memory: 32372kb
input:
4942 877 4180 4180 4409 4409 2233 2233 3491 3491 3459 3459 4501 4501 2192 2192 3539 3539 4379 4379 4346 4346 1553 1553 2100 2100 3426 3426 3461 3461 811 811 2981 2981 1493 1493 610 610 599 599 1741 1741 3216 3216 1646 1646 1016 1016 3757 3757 2570 2570 2900 2900 4649 4649 1014 1014 538 538 4288 4288...
output:
4236 3338 4942 4942 4942 4942 1551 1272 3885 4140 4942 3627 3132 3991 3157 4024 4942 4942 3761 3064 238 4942 4942 4942 4942 4942 2256 4942 649 4496 4942 4942 4491 866 4208 4942 4942 4726 4942 4462 4942 4942 4234 2676 2593 4942 4088 4942 2704 3344 3560 4942 4942 4461 4511 4634 3437 2884 3842 4942 494...
result:
ok 4910 numbers
Test #5:
score: 7
Accepted
time: 9ms
memory: 32292kb
input:
4996 1 2 2 3 1 4 4 5 4 6 3 7 4 8 8 9 3 10 9 11 5 12 7 13 12 14 8 15 8 16 14 17 10 18 15 19 17 20 15 21 19 22 21 23 14 24 20 25 25 26 21 27 20 28 19 29 29 30 24 31 31 32 29 33 27 34 34 35 31 36 27 37 30 38 35 39 38 40 37 41 34 42 41 43 43 44 42 45 36 46 37 47 47 48 47 49 41 50 50 51 46 52 50 53 51 54...
output:
4869 3419 3000 4640 4996 4996 3854 4165 4542 4996 1758 3584 3011 4996 4996 4383 2064 4199 2786 2470 4759 4996 4657 4157 2443 2594 1823 3215 1635 3908 1903 3207 2153 4448 4996 4996 3071 2649 3452 4996 1235 1599 2732 2244 2311 4618 1250 4577 3498 4941 1058 3498 3539 3415 907 4170 4996 4144 2235 2664 4...
result:
ok 4952 numbers
Test #6:
score: 7
Accepted
time: 3ms
memory: 31940kb
input:
4935 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 5...
output:
4442 4133 346 3268 4850 3512 3312 3581 4092 4655 2256 3950 3157 3480 4935 4188 4935 1593 1135 4935 4935 4875 4108 3771 4158 4935 4935 3156 3148 1814 4935 3368 4303 2861 4917 2370 3992 4764 2772 4935 4935 2640 4935 4691 2291 4268 1798 4530 3058 3219 4935 3141 4935 2699 4547 2164 2495 3049 370 3409 21...
result:
ok 4992 numbers
Test #7:
score: 7
Accepted
time: 0ms
memory: 32244kb
input:
4919 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
2653 3219 4302 1418 1713 713 3341 647 487 1508 971 4851 4443 3078 2380 2267 4171 18 2056 1833 3136 817 4375 4103 3423 433 3967 725 282 2358 4171 1680 3350 2403 802 1855 137 2091 3731 1061 581 1273 4783 133 1911 4239 4233 678 3127 3481 284 1896 435 593 4781 103 4647 1615 1231 2689 574 1833 4783 645 4...
result:
ok 4980 numbers
Test #8:
score: 7
Accepted
time: 8ms
memory: 32052kb
input:
4973 1 4517 2 744 3 1115 4 3191 5 4186 6 4608 7 3898 8 3939 9 1998 10 2287 11 2277 12 4200 13 4935 14 3955 15 3683 16 278 17 547 18 3351 19 2642 20 4050 21 3457 22 2337 23 3435 24 1476 25 4853 26 3985 27 736 28 3016 29 4840 30 3866 31 4567 32 4067 33 3724 34 1872 35 1533 36 4787 37 53 38 1632 39 295...
output:
91 2487 2646 1791 2447 3327 532 1801 1079 1526 1236 77 4028 3401 4103 1573 3540 1641 452 52 2497 3128 2593 734 1293 3213 1786 1626 2130 2033 1935 2673 1758 1838 1284 758 2952 301 947 2875 3073 1462 2615 2842 3561 1969 1416 3088 2476 1082 696 3665 2041 3263 3063 2988 1402 1050 2967 3696 2309 3767 281...
result:
ok 4982 numbers
Subtask #2:
score: 8
Accepted
Test #9:
score: 8
Accepted
time: 357ms
memory: 66024kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
757 69428 2793 181264 91707 182 32496 199183 6399 15975 11640 119051 236 689 15 9532 41 36592 178936 56 45424 193403 90248 3417 949 68 34133 60471 199861 188090 75088 127 1 6 4 3 3 11 61157 199860 199153 155706 196287 192862 53742 51862 179199 428 196282 199989 3613 26 99007 134461 198159 20382 7518...
result:
ok 199996 numbers
Test #10:
score: 8
Accepted
time: 225ms
memory: 64936kb
input:
199993 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
22 31743 62 30 510 6079 94 24063 190 4079 382 30 62 12159 1022 2043 8063 62 4 3063 4079 30 254 46 10 22 6111 12159 16127 22 1 12031 1 94 382 766 4063 254 46 766 1022 62 766 1 22 46 30 8063 8063 254 3063 22 62 30 1 62 254 4 10 15871 1022 46 2039 6079 22 254 1022 16127 30 766 8127 14 14 10 46 1 62 406...
result:
ok 199995 numbers
Test #11:
score: 8
Accepted
time: 580ms
memory: 76584kb
input:
199993 25163 125238 125238 19096 19096 88864 88864 113505 113505 12722 12722 56225 56225 8736 8736 74926 74926 38529 38529 80231 80231 19719 19719 198784 198784 75213 75213 190174 190174 163340 163340 62363 62363 144160 144160 130912 130912 3919 3919 21218 21218 85281 85281 187312 187312 79930 79930...
output:
97095 57496 116181 132482 144412 69917 174677 96334 37980 80902 148979 22074 166530 153392 43419 163281 148526 62703 79363 199993 153733 152298 5085 156125 117973 61925 36346 95741 124148 102890 20093 5408 77598 176994 177809 169850 144418 43786 189237 69098 5167 199993 103575 105198 197612 38829 20...
result:
ok 199994 numbers
Test #12:
score: 8
Accepted
time: 488ms
memory: 96588kb
input:
200000 3219 118490 118490 61372 61372 74390 74390 88375 88375 63918 63918 37580 37580 33219 33219 170480 170480 81737 81737 153202 153202 93921 93921 149109 149109 88339 88339 167037 167037 67099 67099 58363 58363 6784 6784 109386 109386 11895 11895 14872 14872 65638 65638 43958 43958 181669 181669 ...
output:
59633 108235 72863 144596 90365 57521 48069 163045 124462 18633 39115 111210 59413 80420 86945 182373 99188 57011 148702 53778 132289 68037 69705 50797 91155 77852 27499 106082 87174 122445 78221 71755 10125 93101 163451 16175 104215 50130 81182 30091 44299 81429 91045 111890 73099 72278 74017 59177...
result:
ok 199992 numbers
Test #13:
score: 8
Accepted
time: 371ms
memory: 72504kb
input:
199992 1 2 1 3 2 4 2 5 4 6 1 7 5 8 5 9 3 10 6 11 4 12 4 13 6 14 5 15 9 16 11 17 17 18 13 19 18 20 14 21 18 22 17 23 21 24 19 25 25 26 25 27 27 28 21 29 20 30 29 31 23 32 31 33 33 34 34 35 28 36 33 37 28 38 38 39 30 40 33 41 33 42 38 43 41 44 44 45 44 46 41 47 45 48 41 49 47 50 49 51 42 52 50 53 44 5...
output:
40732 40074 40815 13444 89657 22422 23494 61358 102922 66209 62228 32272 77095 68562 27799 74336 45129 71632 68525 13022 71347 63735 92178 64200 90446 50728 83632 61441 43695 10496 35481 81587 75266 77943 56182 14188 46302 108160 84166 3192 52959 522 57676 28165 97982 15371 95012 3437 53633 49240 55...
result:
ok 199998 numbers
Test #14:
score: 8
Accepted
time: 251ms
memory: 84296kb
input:
199990 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
59224 71441 128293 104009 42824 136779 12532 93560 81095 108628 176617 63487 103752 175849 36193 178489 73311 34313 46423 75989 76344 145231 20076 127399 81148 17356 39455 99025 44904 3548 78503 135455 28 136931 58140 53161 33288 134084 67877 26048 51868 74301 139992 165315 126781 136117 28112 86333...
result:
ok 199996 numbers
Test #15:
score: 8
Accepted
time: 204ms
memory: 64688kb
input:
199997 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
65710 203 400 304 388 328 441 19 417 49 311 329 193 71968 895 179 152645 282 7600 185 150933 150045 444 3693 56770 34420 8765 335 73751 4665 3 203 380 44479 392 356 113 373 46663 143312 234 265 386 378 339 184360 404 21904 9861 393 445 441 91 299 9 213 24586 65263 22235 121 35761 169 36121 435 40035...
result:
ok 199995 numbers
Test #16:
score: 8
Accepted
time: 585ms
memory: 66176kb
input:
199997 1 64008 2 4187 3 154904 4 191579 5 107782 6 29053 7 123085 8 191601 9 95335 10 164039 11 171804 12 145532 13 104884 14 19820 15 74055 16 14172 17 98802 18 144668 19 188276 20 173096 21 62815 22 133749 23 65035 24 161785 25 191028 26 84730 27 176488 28 173295 29 110316 30 121532 31 81037 32 81...
output:
135622 123942 47301 113894 93180 10469 9237 13166 2896 20323 182669 26483 168662 47202 7900 7785 129591 1577 17943 5638 16670 16980 32760 153668 394 142656 30298 1801 167880 25099 10860 39103 28660 158337 55 126816 57661 17387 11147 95051 3 13130 28040 163801 141 109445 110915 13173 56634 20527 6325...
result:
ok 199993 numbers
Subtask #3:
score: 23
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 23
Accepted
time: 396ms
memory: 73244kb
input:
199996 1 2 2 3 3 4 1 5 1 6 4 7 1 8 5 9 4 10 4 11 7 12 11 13 7 14 10 15 2 16 1 17 9 18 10 19 9 20 13 21 8 22 14 23 21 24 8 25 20 26 23 27 17 28 6 29 9 30 9 31 14 32 14 33 6 34 7 35 35 36 31 37 37 38 2 39 12 40 16 41 18 42 3 43 27 44 4 45 7 46 24 47 16 48 44 49 10 50 11 51 9 52 16 53 39 54 30 55 4 56 ...
output:
190330 676 6 462 40 5 180041 3 9236 4 7780 72 19848 100092 66812 28617 39645 66797 22 12 957 2542 7 68308 382 96 217 50 44 227 12909 1519 54616 1682 27 124101 45 12279 173381 10 33 21516 147537 59 40 5332 183402 67257 4281 7 172420 498 154897 113480 208 174 1 497 172594 1098 788 13628 39540 3716 748...
result:
ok 199999 numbers
Test #18:
score: 23
Accepted
time: 255ms
memory: 74736kb
input:
199996 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1533 3063 6 30 23551 15871 15871 24063 30 16127 1022 12159 10 1021 254 14 190 12159 510 1533 190 8127 3055 1022 94 24063 766 766 94 254 38 62 8063 10 6 22 1533 24063 1531 1022 30 4079 6079 766 16127 190 2043 8127 510 62 126 8063 126 126 48444 15871 4079 16 6111 22 6 10 78 30 254 94 15871 4 254 1021 ...
result:
ok 200000 numbers
Test #19:
score: 23
Accepted
time: 592ms
memory: 90496kb
input:
199995 11041 115179 115179 153668 153668 847 847 108504 108504 29146 29146 69344 69344 97959 97959 9751 9751 161877 161877 181430 181430 34952 34952 189883 189883 115070 115070 183758 183758 82663 82663 166540 166540 32583 32583 98368 98368 134401 134401 177593 177593 20320 20320 84802 84802 71314 7...
output:
130387 9664 11547 91275 69020 68292 133814 4062 77306 61282 135928 73117 110236 103657 45122 57716 71794 147915 130944 51863 118043 70186 3280 145614 126093 73581 69331 53113 47390 148553 125773 9218 4978 58747 152237 79990 104530 37955 88353 26213 133365 186683 125906 71589 170278 141966 124506 906...
result:
ok 199990 numbers
Test #20:
score: 23
Accepted
time: 505ms
memory: 85204kb
input:
199993 177390 147612 147612 4211 4211 14815 14815 169902 169902 107796 107796 87432 87432 66581 66581 144789 144789 48284 48284 124832 124832 151850 151850 145877 145877 31550 31550 71569 71569 63733 63733 951 951 6788 6788 199487 199487 114893 114893 11399 11399 170687 170687 122411 122411 46734 46...
output:
107762 141285 24282 123780 66318 114627 45030 82414 56308 6384 104567 96050 91967 43940 151582 70456 69859 121641 60747 102655 183088 79543 155264 136617 108988 104594 43276 168667 110178 40707 29012 62994 22555 14804 27491 65920 22536 58571 192497 122141 47921 104042 112261 96620 126104 111319 9733...
result:
ok 199994 numbers
Test #21:
score: 23
Accepted
time: 405ms
memory: 79244kb
input:
199993 1 2 1 3 2 4 1 5 3 6 1 7 5 8 7 9 9 10 7 11 3 12 6 13 4 14 5 15 8 16 14 17 10 18 10 19 15 20 20 21 19 22 13 23 15 24 17 25 22 26 26 27 20 28 28 29 21 30 21 31 25 32 23 33 25 34 31 35 28 36 30 37 34 38 31 39 34 40 36 41 32 42 37 43 42 44 39 45 42 46 41 47 38 48 43 49 40 50 42 51 50 52 49 53 47 5...
output:
51578 38667 1524 13459 21140 3826 59246 2246 47429 55781 53983 77239 20185 106208 53791 70701 8913 35683 57133 100232 55601 50968 69940 56442 18980 6305 94853 29355 52681 96168 83317 11505 21769 51959 100713 61485 514 47185 100363 84120 36280 64865 55201 65700 7318 24265 82609 20438 5870 73828 86460...
result:
ok 199992 numbers
Test #22:
score: 23
Accepted
time: 311ms
memory: 93712kb
input:
199996 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
61674 63693 5444 4412 119192 97999 68341 140082 55497 42858 77523 54267 167822 49345 20816 48970 131851 179687 94880 43274 93973 118005 52804 91728 102191 94963 103067 30400 99910 161391 7340 68917 67420 88327 12228 104409 151035 80497 90523 116958 77993 61410 100229 69813 145161 121525 19553 14452 ...
result:
ok 199992 numbers
Test #23:
score: 23
Accepted
time: 204ms
memory: 64904kb
input:
199991 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
59 48 415 291 69 119538 321 272 334 54 214 41286 367 13805 97857 104 241 255 283 91 323 161 357 125045 132 339 151823 80847 65651 115686 29503 218 53641 258 23 77332 288 45 73 66967 152 299 23692 98685 75 131750 139781 98 350 357 26 4232 254 178 57217 77332 239 448 11508 264 16540 398 117035 405 14 ...
result:
ok 199993 numbers
Test #24:
score: 23
Accepted
time: 611ms
memory: 76352kb
input:
199995 1 113414 2 2284 3 98845 4 44695 5 160127 6 100466 7 194555 8 16596 9 144228 10 80166 11 163524 12 104617 13 156298 14 190763 15 190200 16 51669 17 159037 18 3883 19 169292 20 129486 21 109285 22 177749 23 42088 24 110131 25 34729 26 20820 27 157541 28 11756 29 138395 30 24135 31 153422 32 191...
output:
109204 39278 62211 134886 9 601 181082 41676 2033 116851 72120 27639 11577 38351 77170 54255 33378 82327 102402 74545 8152 64128 31796 148495 415 54543 1354 47764 41935 52287 142939 122745 32683 1725 170345 41430 20010 48221 24637 34819 153209 10982 113155 18968 34947 162078 2043 106717 190000 1108 ...
result:
ok 199999 numbers
Subtask #4:
score: 22
Accepted
Test #25:
score: 22
Accepted
time: 433ms
memory: 98776kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
78 107329 190250 5672 110415 199160 3826 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 192719 99 191654 80328 481 195140 170809 120515 290 199616 719 142 195166 2607 20737 135444 199768 2433 164666 180527 198261 14511 53672 69060 185790 110874 639 131 2130 188357 150164 2...
result:
ok 199996 numbers
Test #26:
score: 22
Accepted
time: 393ms
memory: 119740kb
input:
199992 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1471 48440 199992 231 2687 31 114687 114687 13823 114 106495 163839 783 25599 199992 12799 73727 199992 431 196607 26623 414 27960 22 11135 60728 7551 167224 199992 231 199992 77823 25599 199992 15359 163839 15359 167224 113 4735 1439 45055 163839 391 56632 2159 24063 65 1439 383 62 57 1327 163839 4...
result:
ok 199992 numbers
Test #27:
score: 22
Accepted
time: 569ms
memory: 83236kb
input:
199999 3860 158798 158798 118869 118869 87485 87485 146359 146359 191153 191153 55478 55478 180863 180863 50335 50335 96889 96889 48813 48813 98038 98038 187938 187938 87677 87677 134328 134328 38608 38608 80793 80793 70631 70631 193550 193550 97635 97635 158355 158355 67072 67072 186681 186681 1915...
output:
55240 49943 26982 45606 18199 8540 11154 152784 18240 110004 99804 184499 25817 43162 59012 69553 1005 100567 48973 134533 3623 46254 103686 19321 49467 116243 148782 4728 73635 54046 50253 112743 41598 15497 31081 115955 73228 101666 12285 66903 165797 10283 7127 8495 56070 15396 6405 64423 109109 ...
result:
ok 200000 numbers
Test #28:
score: 22
Accepted
time: 479ms
memory: 97220kb
input:
199999 59863 94723 94723 191248 191248 161438 161438 39858 39858 77973 77973 71710 71710 106785 106785 362 362 86462 86462 133116 133116 123399 123399 4410 4410 92447 92447 47116 47116 51368 51368 1717 1717 15475 15475 40375 40375 180726 180726 185474 185474 93281 93281 27126 27126 126163 126163 185...
output:
28854 18939 99436 18961 67220 2913 72453 29640 46298 117130 151058 159698 48935 29930 80292 81462 64883 160737 96248 31383 139115 37518 45423 96863 4355 49922 35109 35647 43119 13322 143399 69774 113511 24821 58074 64681 120987 92287 36356 125547 47395 59340 70057 24681 70093 32217 92486 151556 272 ...
result:
ok 199998 numbers
Test #29:
score: 22
Accepted
time: 413ms
memory: 85144kb
input:
199999 1 2 1 3 1 4 3 5 5 6 3 7 3 8 7 9 4 10 5 11 7 12 4 13 12 14 9 15 7 16 14 17 12 18 9 19 16 20 18 21 15 22 20 23 16 24 17 25 23 26 20 27 20 28 19 29 23 30 30 31 30 32 24 33 26 34 31 35 27 36 34 37 34 38 36 39 31 40 36 41 39 42 36 43 39 44 38 45 44 46 38 47 40 48 48 49 45 50 46 51 49 52 46 53 49 5...
output:
179063 34801 103836 135654 64719 31996 62273 36156 57204 102674 112750 26298 26560 36095 4538 136764 59099 25262 22520 2188 326 124414 49430 104026 13192 107883 19919 11694 36861 12879 46288 44653 63915 43067 53333 25512 51864 95866 48607 75013 30475 45557 43145 122747 1292 92281 16134 106448 96618 ...
result:
ok 199996 numbers
Test #30:
score: 22
Accepted
time: 275ms
memory: 90304kb
input:
199995 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
11322 92512 102000 97896 20730 48162 17704 111224 70792 61672 38774 3548 82674 7220 63754 48942 110298 166606 80194 89338 20980 39184 530 64760 57858 74920 4682 32684 103882 62806 138544 57050 47356 20632 13396 76936 14736 49600 169188 141804 62220 9794 7876 87336 70928 4802 88372 38652 33414 57390 ...
result:
ok 199999 numbers
Test #31:
score: 22
Accepted
time: 189ms
memory: 70452kb
input:
199997 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
1782 4982 5806 6770 3651 1082 268 2432 3191 6471 5869 3261 7666 2045 2623 5952 6615 4034 2808 1757 1553 8402 5288 1726 3113 9374 8519 4150 7828 9439 8409 6435 9101 3764 3702 503 151 7328 6347 6911 6963 2134 3879 6229 7721 6562 4477 1305 8052 4024 6810 7220 5699 8918 6330 1719 3279 3201 6052 7004 621...
result:
ok 199999 numbers
Test #32:
score: 22
Accepted
time: 656ms
memory: 92576kb
input:
199999 1 133395 2 64415 3 65341 4 81009 5 84535 6 162775 7 10569 8 14377 9 16311 10 131379 11 199183 12 64100 13 71522 14 115723 15 167988 16 184640 17 163581 18 20948 19 25356 20 107507 21 9188 22 137361 23 2343 24 110749 25 28698 26 136381 27 19371 28 44461 29 6620 30 81748 31 199467 32 23686 33 4...
output:
5308 12623 377 5650 2217 3364 8277 11398 3252 6806 9983 2090 9100 7471 20364 1528 7894 593 8848 3908 4789 3727 2719 9300 5056 2535 7723 3027 9920 14537 6965 6119 13888 10319 6801 2961 4206 8834 8531 14022 2293 3721 3857 9070 7956 2671 1097 8434 4441 2794 9169 3865 1060 2150 8676 175 5869 8878 7828 9...
result:
ok 199992 numbers
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #33:
score: 20
Accepted
time: 85ms
memory: 49416kb
input:
49994 1 2 1 3 1 4 4 5 4 6 2 7 5 8 2 9 5 10 3 11 11 12 5 13 2 14 5 15 14 16 15 17 15 18 11 19 7 20 2 21 1 22 21 23 15 24 22 25 16 26 22 27 16 28 11 29 17 30 21 31 3 32 22 33 3 34 33 35 34 36 17 37 22 38 21 39 22 40 11 41 14 42 30 43 42 44 27 45 41 46 21 47 5 48 17 49 40 50 31 51 23 52 40 53 17 54 39 ...
output:
49991 27842 12698 41582 41674 49129 139 49931 49986 49966 33701 41907 520 7 49823 37296 45378 43279 22 45415 43709 139 1658 12239 1106 48337 42014 49964 1603 49935 1295 38134 484 49771 13800 36652 12183 1503 49825 148 49211 195 46766 38915 49990 26440 26888 1176 140 37080 8196 5750 49964 49612 49935...
result:
ok 49997 numbers
Test #34:
score: 20
Accepted
time: 75ms
memory: 52636kb
input:
49994 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27...
output:
13823 49994 49994 24 367 48 19455 367 2175 6655 1215 3839 17407 9727 49994 28671 49994 3039 49994 49151 1071 3839 3839 49994 1215 49994 671 3839 49994 591 3711 49994 15359 49994 28 2175 367 28671 10751 49994 11263 98 107 41802 4543 199 36863 49994 49994 1183 367 49151 40959 1071 2111 6655 11263 1927...
result:
ok 49997 numbers
Test #35:
score: 20
Accepted
time: 111ms
memory: 46388kb
input:
49992 18276 49801 49801 29872 29872 18038 18038 5160 5160 47615 47615 9368 9368 48020 48020 18919 18919 22293 22293 28784 28784 26366 26366 16335 16335 996 996 28965 28965 7132 7132 9570 9570 22976 22976 16634 16634 22619 22619 28051 28051 11004 11004 1360 1360 41340 41340 43214 43214 24436 24436 46...
output:
46017 14490 35283 47122 47076 47522 33249 14538 36480 29309 30496 22079 35856 47676 19688 29847 49992 46968 30446 36597 41074 24827 42181 37491 49992 33422 23462 34849 43986 32605 22539 43614 40945 48216 9983 37908 40591 47737 22962 33035 23333 35206 19572 33241 18254 44132 21667 21688 43981 44138 3...
result:
ok 49996 numbers
Test #36:
score: 20
Accepted
time: 93ms
memory: 49144kb
input:
49991 36788 8430 8430 29122 29122 7462 7462 34863 34863 38520 38520 38159 38159 10299 10299 26846 26846 40569 40569 35453 35453 39237 39237 37963 37963 2323 2323 5574 5574 49072 49072 8151 8151 9543 9543 14269 14269 15375 15375 38098 38098 46141 46141 29199 29199 13837 13837 3056 3056 13396 13396 20...
output:
10717 26965 17476 49991 49991 12680 32753 49991 44617 49991 49991 49991 49991 29760 49991 49991 49991 49991 49991 49991 15545 49991 19088 21948 23809 49991 46952 49991 49991 49991 36059 37144 49991 49991 41837 49991 49991 49991 49991 49991 49991 49991 49991 49991 49991 49991 28977 43912 49991 49991 ...
result:
ok 49999 numbers
Test #37:
score: 20
Accepted
time: 85ms
memory: 44912kb
input:
49992 1 2 1 3 3 4 4 5 5 6 6 7 6 8 3 9 9 10 4 11 7 12 6 13 7 14 9 15 10 16 8 17 13 18 18 19 15 20 17 21 19 22 13 23 23 24 21 25 19 26 19 27 23 28 19 29 25 30 27 31 28 32 25 33 30 34 34 35 28 36 32 37 35 38 36 39 34 40 39 41 41 42 39 43 34 44 41 45 36 46 44 47 39 48 48 49 44 50 43 51 44 52 49 53 53 54...
output:
49992 44208 40560 49983 44985 19872 12959 21712 45703 31309 33201 49992 21924 36480 16502 31883 16181 36221 24725 42191 49992 35236 49992 35558 23642 20260 20165 11056 7575 49992 47236 49992 49992 43883 49992 35916 44169 49992 32253 41307 11731 4410 36173 36842 41712 18415 15542 34255 14712 35964 31...
result:
ok 49997 numbers
Test #38:
score: 20
Accepted
time: 57ms
memory: 45220kb
input:
49992 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 ...
output:
39583 37249 43384 29100 15677 17788 5806 32912 32417 42927 35958 35935 20363 17412 28393 13083 49992 17231 44476 34557 26645 31001 33105 49992 42169 38467 49992 34467 22711 30648 32377 40585 16552 48257 37613 16909 35471 49992 25468 18922 26730 24191 41997 49299 41755 17953 37963 49992 2358 9448 499...
result:
ok 49991 numbers
Test #39:
score: 20
Accepted
time: 39ms
memory: 44536kb
input:
49992 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53...
output:
2119 8453 47550 40224 8275 48438 21511 29343 11178 12840 37338 17769 49992 40224 26178 11775 11405 48882 23283 9518 26016 49548 36450 8684 22461 35730 41556 10352 38656 26589 8503 36628 20425 46879 43554 47994 15804 12373 28369 21219 43776 38004 38886 35562 20679 5674 16613 25704 29120 2178 21055 31...
result:
ok 49990 numbers
Test #40:
score: 20
Accepted
time: 123ms
memory: 46772kb
input:
49996 1 34528 2 1933 3 8542 4 37866 5 13181 6 33418 7 31611 8 9600 9 47851 10 22729 11 34920 12 20679 13 13874 14 35815 15 1308 16 40327 17 20697 18 34642 19 45144 20 40726 21 36899 22 49440 23 42507 24 34983 25 34496 26 41651 27 19121 28 30392 29 48080 30 18302 31 28030 32 22472 33 26275 34 17680 3...
output:
177 25075 32138 400 36791 38592 28612 12464 10352 43337 36452 43158 13659 5593 29988 23224 7087 23922 25697 21833 5923 44766 33658 16893 26217 30297 37628 43546 12097 2042 26157 34289 36173 22194 3792 36001 44332 6645 23987 19246 32699 8178 25580 8650 32659 39845 21279 24361 32241 26532 20586 3931 3...
result:
ok 49996 numbers
Subtask #6:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #41:
score: 20
Accepted
time: 453ms
memory: 99264kb
input:
199998 1 2 1 3 1 4 3 5 3 6 1 7 5 8 2 9 7 10 7 11 5 12 10 13 9 14 4 15 14 16 7 17 7 18 14 19 2 20 9 21 15 22 19 23 11 24 2 25 2 26 17 27 9 28 8 29 22 30 29 31 4 32 4 33 23 34 12 35 31 36 6 37 4 38 25 39 30 40 21 41 28 42 15 43 1 44 32 45 29 46 31 47 39 48 8 49 44 50 16 51 19 52 9 53 32 54 26 55 50 56...
output:
179995 108586 4963 70151 689 198956 197533 15818 172427 118 52593 199983 198743 199323 162610 144870 162893 36041 525 199998 6091 15211 199998 199939 1707 199993 33565 199838 115776 198285 195716 2734 126920 199940 196726 196524 47829 199558 114808 18326 197686 14180 1394 19 191283 176946 5606 124 1...
result:
ok 199999 numbers
Test #42:
score: 20
Accepted
time: 385ms
memory: 122000kb
input:
199992 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
199992 56 199992 13055 11135 199992 163839 431 799 199992 727 199992 199992 431 4863 1471 196607 199992 33 2367 199992 1471 106495 199992 1471 199992 199992 199992 199992 9151 199992 2623 199992 231 199992 199992 199992 783 431 45055 199992 26623 423 431 14847 199992 34815 90111 1083 431 199992 1999...
result:
ok 199992 numbers
Test #43:
score: 20
Accepted
time: 555ms
memory: 86220kb
input:
200000 118825 47656 47656 65863 65863 74743 74743 199221 199221 111383 111383 107539 107539 47816 47816 169853 169853 102993 102993 101994 101994 33240 33240 25914 25914 69791 69791 77751 77751 120707 120707 172811 172811 193635 193635 18418 18418 10680 10680 47074 47074 197767 197767 150332 150332 ...
output:
200000 64650 93758 56301 50503 118402 148383 83228 129609 90886 75758 200000 69251 127325 159115 118795 150796 166706 64322 153404 150739 50524 112623 158834 196078 64809 116702 145625 150839 83880 138037 173583 127876 72942 102044 155630 200000 112467 196660 177109 132219 70774 134923 190720 76880 ...
result:
ok 199993 numbers
Test #44:
score: 20
Accepted
time: 497ms
memory: 101220kb
input:
200000 140177 147015 147015 80766 80766 173562 173562 145745 145745 115382 115382 81887 81887 134802 134802 31260 31260 42937 42937 3026 3026 143880 143880 70228 70228 106613 106613 64162 64162 73444 73444 158592 158592 127118 127118 134344 134344 120280 120280 80902 80902 103224 103224 124428 12442...
output:
200000 200000 59622 91201 68717 200000 151534 84875 149153 200000 41840 200000 200000 158096 106034 89586 200000 200000 154987 54783 124204 151075 183769 200000 200000 200000 110986 186654 151730 180598 200000 200000 167338 200000 200000 200000 181651 165751 158064 200000 83213 200000 17633 200000 7...
result:
ok 199999 numbers
Test #45:
score: 20
Accepted
time: 418ms
memory: 86368kb
input:
199996 1 2 1 3 3 4 3 5 1 6 4 7 2 8 7 9 1 10 8 11 6 12 6 13 4 14 13 15 10 16 12 17 8 18 9 19 18 20 16 21 17 22 22 23 22 24 18 25 18 26 25 27 20 28 21 29 26 30 28 31 25 32 29 33 28 34 28 35 29 36 29 37 35 38 36 39 34 40 39 41 34 42 40 43 41 44 43 45 38 46 42 47 41 48 39 49 44 50 43 51 46 52 48 53 51 5...
output:
102287 62949 83320 78317 119816 120129 175292 197099 153372 83521 118966 89093 116052 62696 134790 108942 69628 193383 123944 151060 27792 71146 109472 81289 68534 85601 125191 58074 90875 58204 143224 131193 105748 196859 68706 174117 134837 53880 84743 98881 177935 61478 123596 199996 55478 107385...
result:
ok 199993 numbers
Test #46:
score: 20
Accepted
time: 295ms
memory: 91296kb
input:
199998 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50...
output:
186807 109497 139615 191555 184979 162897 124317 103761 187612 57874 68832 121596 141626 160741 48560 109825 199998 32708 199998 102262 199998 173769 46050 126461 101135 32016 199998 199998 125655 131367 199998 119037 186247 199998 94814 142975 139522 56868 199998 103410 33688 143220 156222 153369 1...
result:
ok 199998 numbers
Test #47:
score: 20
Accepted
time: 192ms
memory: 71032kb
input:
199992 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
48861 134946 43510 54859 148817 190647 96145 183527 36169 18973 13027 68842 106516 136659 172809 97806 6923 65669 158162 82067 94501 119877 173292 118474 127433 171957 52421 175517 148807 130127 10699 116764 52985 165727 193317 158162 93183 36616 58892 164392 10328 28633 116277 145209 121227 70707 1...
result:
ok 199996 numbers
Test #48:
score: 20
Accepted
time: 695ms
memory: 97728kb
input:
199998 1 18131 2 108742 3 195033 4 176233 5 48568 6 43435 7 141282 8 149515 9 33524 10 51760 11 192173 12 12860 13 23308 14 32202 15 85869 16 126977 17 95377 18 66385 19 57539 20 116394 21 127394 22 170730 23 70332 24 135810 25 31748 26 131929 27 30606 28 149494 29 82156 30 179350 31 25065 32 11486 ...
output:
29024 185228 193197 130227 91464 160018 124481 32790 186358 174038 56523 108354 110289 94210 108442 72790 161588 163272 96168 65303 58425 65093 169744 150289 6440 60395 146279 4201 165286 44100 106156 17362 45113 85568 61972 139648 26506 100065 6858 166513 71469 147775 5859 34022 174902 104135 14275...
result:
ok 199991 numbers