QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303551 | #4924. 蜘蛛爬树 | zyc070419 | 31 | 1452ms | 176220kb | C++14 | 8.1kb | 2024-01-12 18:12:40 | 2024-01-12 18:12:40 |
Judging History
answer
#include <bits/stdc++.h>
#define INF 9e18
#define inf 1e9
#define ll long long
using namespace std;
const int N = 2e5 + 3;
inline int read() {
char ch = getchar(); int x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
inline ll Read() {
char ch = getchar(); ll x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
struct Node {
int id, d;
Node(int a = 0, int b = 0) {id = a; d = b;}
};
struct NOde {
int id, l, r, d;
NOde(int a = 0, int b = 0, int c = 0, int D = 0) {id = a; l = b; r = c; d = D;}
};
struct NODe {
int id, d, x;
NODe(int a = 0, int b = 0, int c = 0) {id = a; d = b; x = c;}
};
int n, m, T, a[N];
int depth[N], fa[N], sz[N], son[N], id[N], num, top[N];
ll dis[N], now[N], ans[N], len[N];
vector< pair<int, ll> > g[N];
vector<Node> mem[N], vec[N];
vector<NODe> fuc[N];
vector<NOde> ex[N];
struct LC_Segment_Tree {
struct node {
int ls, rs, k; ll b;
node() {ls = rs = k = 0; b = INF;}
}t[N * 20];
int tot, fir;
inline ll f(int x, int k, ll b) {return 1ll * k * x + b;}
void update(int &rt, int l, int r, int k, ll b) {
if (!rt) {
rt = ++tot;
t[tot].k = k; t[tot].b = b;
return;
}
int mid = (l + r) >> 1;
if (f(mid, k, b) < f(mid, t[rt].k, t[rt].b)) swap(k, t[rt].k), swap(b, t[rt].b);
if (l == r) return;
if (f(l, k, b) < f(l, t[rt].k, t[rt].b)) update(t[rt].ls, l, mid, k, b);
if (f(r, k, b) < f(r, t[rt].k, t[rt].b)) update(t[rt].rs, mid + 1, r, k, b);
}
ll query(int rt, int l, int r, int x) {
if (!rt) return INF;
if (l == r) return f(x, t[rt].k, t[rt].b);
int mid = (l + r) >> 1; ll res = f(x, t[rt].k, t[rt].b);
if (x <= mid) res = min(res, query(t[rt].ls, l, mid, x));
else res = min(res, query(t[rt].rs, mid + 1, r, x));
return res;
}
void init() {
for (int i = 0; i <= tot; ++i) t[i] = node();
tot = fir = 0;
}
}t;
struct Segment_Tree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
int root[N << 2];
void update(int rt, int l, int r, int pos, int k, ll b) {
t.update(root[rt], 0, inf, k, b);
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) update(ls, l, mid, pos, k, b);
else update(rs, mid + 1, r, pos, k, b);
}
ll query(int rt, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) return t.query(root[rt], 0, inf, x);
int mid = (l + r) >> 1; ll res = INF;
if (ql <= mid) res = min(res, query(ls, l, mid, ql, qr, x));
if (qr > mid) res = min(res, query(rs, mid + 1, r, ql, qr, x));
return res;
}
void build(int rt, int l, int r) {
root[rt] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
}
void init(int l, int r) {
build(1, l, r);
t.init();
}
#undef ls
#undef rs
}tt;
void dfs1(int x, int pa, int d) {
depth[x] = d; fa[x] = pa; sz[x] = 1;
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == pa) continue;
dis[y] = dis[x] + tmp.second;
dfs1(y, x, d + 1);
sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
}
void dfs2(int x, int anc) {
id[x] = ++num; top[x] = anc;
if (son[x]) dfs2(son[x], anc);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
void Update(int x) {
t.update(t.fir, 0, inf, a[x], dis[x] + dis[x]);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x]) continue;
Update(y);
}
}
void update(int x, ll val) {
t.update(t.fir, 0, inf, a[x], dis[x] + dis[x] - val - val);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x]) continue;
update(y, val);
}
}
void dfs3(int x) {
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
dfs3(y); t.init();
}
if (son[x]) dfs3(son[x]);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
Update(y);
}
t.update(t.fir, 0, inf, a[x], dis[x] + dis[x]);
for (auto tmp : mem[x]) ans[tmp.id] = min(ans[tmp.id], t.query(t.fir, 0, inf, tmp.d) - dis[x] - dis[x]);
for (auto tmp : vec[x]) ans[tmp.id] = min(ans[tmp.id], t.query(t.fir, 0, inf, tmp.d) - dis[x] - dis[x]);
}
void dfs4(int x) {
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
update(y, dis[x]);
}
t.update(t.fir, 0, inf, a[x], 0);
for (auto tmp : mem[x]) ans[tmp.id] = min(ans[tmp.id], t.query(t.fir, 0, inf, tmp.d));
if (son[x]) dfs4(son[x]);
else t.init();
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
dfs4(y);
}
}
void UPdate(int x, int anc) {
t.update(t.fir, 0, inf, a[x], (dis[x] - dis[anc] - dis[anc]) * 2);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x]) continue;
UPdate(y, anc);
}
}
void dfs5(int x) {
t.update(t.fir, 0, inf, a[x], -dis[x] - dis[x]);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
UPdate(y, x);
}
for (auto tmp : fuc[x]) ans[tmp.id] = min(ans[tmp.id], t.query(t.fir, 0, inf, tmp.d) + dis[tmp.x] + dis[tmp.x]);
if (son[x]) dfs5(son[x]);
else t.init();
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
dfs5(y);
}
}
void Update(int x, int L, int R, int anc) {
tt.update(1, L, R, id[anc], a[x], (dis[x] - dis[anc]) << 1);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x]) continue;
Update(y, L, R, anc);
}
}
int main() {
n = read(); m = read(); T = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i < n; ++i) {
int x = read(), y = read(); ll v = Read();
g[x].push_back(make_pair(y, v));
g[y].push_back(make_pair(x, v));
}
dfs1(1, 1, 1); dfs2(1, 1);
for (int i = 1; i <= T; ++i) {
ll xx = Read() - 1, yy = Read() - 1;
int x = xx % n + 1, y = yy % n + 1, d = xx / n - yy / n;
if (d < 0) d = -d;
int fx = x, fy = y;
while (top[fx] != top[fy]) {
if (depth[top[fx]] < depth[top[fy]]) swap(fx, fy);
mem[fx].push_back(Node(i, d));
fx = fa[top[fx]];
}
if (id[fx] > id[fy]) swap(fx, fy);
if (fx == top[fx]) mem[fy].push_back(Node(i, d));
else {
ex[top[fx]].push_back(NOde(i, id[fx], id[fy], d));
vec[fy].push_back(Node(i, d));
}
len[i] = dis[x] + dis[y] - dis[fx] - dis[fx];
ans[i] = INF;
int uuu = fx;
fuc[fx].push_back(NODe(i, d, uuu));
while (top[fx] != 1) {
fx = fa[top[fx]];
fuc[fx].push_back(NODe(i, d, uuu));
}
}
dfs3(1); t.init(); dfs4(1); dfs5(1);
for (int i = 1, x, L, R; i <= n; ++i) {
if (ex[i].empty()) continue;
x = i;
while (son[x]) x = son[x];
tt.init(L = id[i], R = id[x]);
x = i;
while (x) {
tt.update(1, L, R, id[x], a[x], 0);
for (auto tmp : g[x]) {
int y = tmp.first;
if (y == fa[x] || y == son[x]) continue;
Update(y, L, R, x);
}
x = son[x];
}
for (auto tmp : ex[i]) ans[tmp.id] = min(ans[tmp.id], tt.query(1, L, R, tmp.l, tmp.r, tmp.d));
}
for (int i = 1; i <= T; ++i) printf("%lld\n", ans[i] + len[i]);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 11ms
memory: 123096kb
input:
97 99 1000 763118300 558295517 80676328 362318619 473105413 468927175 311496507 936935430 176032966 304576040 308583326 681580095 549392233 518152994 829474320 751189715 542810029 587869244 878512027 530678371 832766129 535259635 799122942 596982955 884696876 605325753 495661541 506105495 561218313 ...
output:
6130845802041 10806758605627 3440559556796 5426989115608 4458875959622 1566659300400 7908007295597 1846030561682 5112206409383 6968388472340 4706970599850 5270158948178 4633066810868 3176122148295 2331646415266 961435137842 14353365296423 9675072605938 4256954122467 7333255321628 8376795894537 12319...
result:
ok 1000 lines
Test #2:
score: 0
Accepted
time: 12ms
memory: 121436kb
input:
96 100 1000 31199641 534644486 57980198 794620020 322548308 524438614 467991232 68617179 243820212 229414440 471419229 316085673 271698528 136252783 926625435 615138376 200446739 551914057 483498389 879166147 512229523 45850421 337184110 799426876 46405170 427929494 235848997 861270528 291868400 616...
output:
2436336301732 4467388472930 6498834342013 6450642313333 4049880787954 7509100670176 5831628235154 4150554274586 3112250048344 202594784082 2974050754796 8714737807242 7727115169865 1321297431165 3071603311467 4662413775237 5469193332429 2306749862693 6240860740176 1297819731517 5602374629655 5876108...
result:
ok 1000 lines
Test #3:
score: 0
Accepted
time: 8ms
memory: 120976kb
input:
96 100 1000 557703101 38662752 91559144 406758463 248251717 279124287 667387330 272252891 892434115 281731667 162886140 786660171 350559478 909940602 476034354 78826379 748607300 381191755 708777514 223906483 954905399 405424569 356033791 565979037 5787205 21241249 399771402 280058652 527147793 5875...
output:
80606469890 86777173467 35481695596 11498756054 87983213070 37171191055 33172639202 31451029430 105454750479 31626589074 105218154775 46986908645 14488184465 20368758481 41150521804 57639739744 45269689956 24620398400 51392609182 44732144926 72097558763 13572235163 78364419227 40255815091 1195379951...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 11ms
memory: 121684kb
input:
96 96 1000 651436202 969634688 411838043 313319930 906863003 709869271 467187062 352351954 116039480 172098032 933097773 469945118 162439715 767382758 713254949 387661957 387494696 343642279 730353853 607472395 431993920 231539946 570437226 454446439 941394569 230535263 758579901 173778951 636556431...
output:
81136576805 65057090263 57308140599 70187240654 42682272024 83341639885 53487742661 53219947761 14656518493 18143524741 27930061212 75815621849 67528908552 39936561353 44548681818 122544815339 64143328818 13510734748 16412423500 108236922255 83503599273 53331146110 59331932211 93957710008 3825533077...
result:
ok 1000 lines
Test #5:
score: -3
Wrong Answer
time: 15ms
memory: 122788kb
input:
100 97 1000 9442498 799978686 853182282 938513473 647407813 233204982 473300672 884708491 641608620 453797741 412704210 204494322 711344505 287815571 401113141 110034416 590478367 831110886 255614524 234577289 759353531 774504637 366342991 154214800 692604750 308540773 768713312 121270668 425512518 ...
output:
5006945326 9445360831 13045856109 4494648380 6833826505 3769548416 11380661054 5754815524 8246147623 4801077020 5798520769 1392753490 6948207422 12106173499 6097834765 4210216111 3541517785 5402770609 8790748574 10564152311 2826265999 5688050930 7790838243 2760570076 4835335024 5099967138 3178901350...
result:
wrong answer 128th lines differ - expected: '6184040514', found: '6817234554'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 1118ms
memory: 165796kb
input:
200000 20 200000 679416469 548913625 468159997 137709609 883140368 682558021 473174374 400192350 124143873 825920417 372498686 851213321 822264481 78195915 5427143 453304163 233551905 810910186 810046144 52603791 282167184 385032797 81387991 747194790 917579656 585184539 12659388 249218417 158295502...
output:
920563165 270738856 355012553 363898450 515535908 734168762 81197110 448355845 204186827 966151314 377621564 856252543 311456222 368700872 197258906 567302636 172379629 579171621 1043838058 244996663 621435809 278057792 727463012 573783312 395879848 500677226 891900111 1031612062 771021332 691010101...
result:
wrong answer 8883rd lines differ - expected: '71604485', found: '120307709'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 12
Accepted
time: 679ms
memory: 169440kb
input:
200000 1000000000 200000 28270302 472359923 262785485 923929785 393684160 761485431 72038469 116384740 426631758 437934930 610834083 455314140 734276543 903544756 220163018 756113376 732404264 947339315 109784905 625451008 794076307 818852312 758007217 124450858 674924509 311761991 507260538 7032362...
output:
29294995135992468 9003943574137677 39324997066279292 37544709020512848 57388992119827952 54425124319330092 19450449300737912 25838911017710871 2608104102967357 32395369352281774 5765752637876701 65609495812941401 57820177390587134 1971831067795873 19213682025389514 30244870693646792 3672338761985429...
result:
ok 200000 lines
Test #29:
score: -12
Wrong Answer
time: 651ms
memory: 176220kb
input:
199957 1000000000 199978 484184824 891546207 975734696 100539020 831491149 39172314 864159331 720402805 776042647 843662372 935604278 544595844 393931465 659783207 863682602 900000494 79169772 921429466 469390191 891091094 53691506 616777249 622575840 230565013 939987814 175664187 663514526 67841276...
output:
19959327553591648 32010533345091793 15410299665390255 71446530548310580 42757122329520314 44547359192496305 40421459068680865 12617048458606361 68505071787885633 20229193415512477 3959463349380309 52345766780671421 22183426380065088 29440145261757182 3846326653273891 34476543006148377 40819831884710...
result:
wrong answer 118886th lines differ - expected: '852208017283924', found: '856940100326654'
Subtask #5:
score: 9
Accepted
Test #36:
score: 9
Accepted
time: 276ms
memory: 154264kb
input:
199918 1000000000 199903 1496 2382 3896 3664 1177 1627 2821 4200 3074 3783 2069 4403 629 2610 4991 4074 3033 2798 4333 3501 3667 3064 663 2821 2818 458 2950 4020 2665 3578 63 4855 4941 3492 2423 4510 1489 1018 4829 1912 3133 3174 309 287 2909 4102 4296 4526 3170 3683 4960 4863 4738 2927 2405 3600 44...
output:
1352416884531 1380463318391 923920163167 1525224977139 1405019709299 869269749781 715671043328 876194052054 1358007874327 127994985855 1230162209719 1532026808855 611656467332 1023855959729 414792924571 1316679734677 827308370883 1265411315424 821484360433 1051517948640 837509712760 582943943131 457...
result:
ok 199903 lines
Test #37:
score: 0
Accepted
time: 306ms
memory: 154196kb
input:
200000 1000 200000 809770918 700177243 142627650 840666719 799717263 288840787 130614153 965150450 584417569 833256629 453961603 553430999 842122932 156970995 233405993 462368588 449589390 97217337 576814616 526506175 16887352 919946415 588340411 47310125 508028561 746882745 289969878 38349443 85588...
output:
1585694392495 706038536805 586801212025 729763504879 1121912701709 602929530934 1384874490966 932809860298 1786651350814 1173133997984 642188971333 1847564817170 874110129257 1634207197990 1165001912684 860420326934 364758620851 736767366986 901294347345 1499330839732 451636930949 1002710230684 1556...
result:
ok 200000 lines
Test #38:
score: 0
Accepted
time: 382ms
memory: 154460kb
input:
200000 1000000000 200000 399998482 399998882 643012112 481981456 399998451 475990021 399997292 399997409 399996369 399998092 399998185 399998416 399998701 399997027 399996347 1000000000 411997672 399996237 399997188 402404134 399996973 399998072 459327897 399997196 399997360 606704265 399997369 3999...
output:
56425935917250335 348929904541748910 43150321666095229 218746357373815571 108846332361563136 211578526026780722 142755080047590213 244555928973138123 59355666550218703 274305014995294225 171177308635990844 94566903236734112 84270300399685207 317423517245573254 902979060499211 14514565807335715 18696...
result:
ok 200000 lines
Test #39:
score: 0
Accepted
time: 511ms
memory: 150724kb
input:
199989 1000000000 199949 5101893 2534711 252776 33497 4575476 620658 35790 1061631 1362697 834917 2062598 2789238 2540552 2557066 725856 2407848 4266144 1731334 653868 4676650 235573 2010805 1576557 922173 617762 1140093 387911 618359 2084018 2717580 9938 4014950 411349 3801906 341206 665844 2556003...
output:
376419619600 353028349944 783455928283 427146243318 508001272847 231025894377 614377184831 496116219491 384142701402 337878147372 528478063399 414595122323 604998898988 244135680083 319848781263 358386785447 481117281935 464006706964 356458898506 260105342030 610113746365 259007651455 414991108424 2...
result:
ok 199949 lines
Test #40:
score: 0
Accepted
time: 512ms
memory: 150464kb
input:
200000 1000000000 200000 1101540 573488 61066 1014872 39283 626062 84341 591377 109026 505272 1339 74452 729192 49315 521939 959958 249731 940337 56264 1071790 609623 239862 57448 809987 464526 111430 226312 124386 673550 421690 211347 45875 138962 705453 739456 464892 44238 52980 905593 205558 5198...
output:
655436303263 616441802310 638361564730 586321577191 519122088245 660130086237 389806954608 241891011597 423594953230 510963332372 630353140994 627262451077 339051346548 308888235187 550167732447 354951509166 308776095000 597351022439 625625736560 772346222022 549689478477 667370706484 319926160326 2...
result:
ok 200000 lines
Test #41:
score: 0
Accepted
time: 8ms
memory: 122008kb
input:
1 2 5 1000000000 1 1 1 2 2 1 2 2 1 1
output:
0 1000000000 1000000000 0 0
result:
ok 5 lines
Test #42:
score: 0
Accepted
time: 11ms
memory: 121708kb
input:
2 1 5 2 1 1 2 1000000000000 1 1 1 2 2 2 1 1 2 1
output:
0 1000000000000 0 0 1000000000000
result:
ok 5 lines
Subtask #6:
score: 22
Accepted
Test #43:
score: 22
Accepted
time: 662ms
memory: 154048kb
input:
200000 1000000000 200000 81882094 47220813 43282454 17633207 52769165 4830673 31396360 64793163 9174729 36727563 71268262 24662923 40146030 1430053 62926106 30042905 1330107 81817720 98841078 87766129 51155045 23216268 79896310 66625868 87854925 42976560 86542933 28336449 34932261 19698851 584453 90...
output:
516260625003899 380880451347644 183401242058615 56975236749493 349851829300288 188845759476214 188011317678919 414887287533565 111834744858133 305218494040213 227244584301956 365579485207024 201761449059479 246263150359463 468212144364502 389353276591541 207814284476264 341801277159919 4270404442188...
result:
ok 200000 lines
Test #44:
score: 0
Accepted
time: 547ms
memory: 157152kb
input:
200000 1000000000 200000 885272642 374759028 888606054 718260881 712640799 453067010 847699265 597983546 473777736 340935923 415594372 874762802 957196626 674414761 601425225 628341608 249369250 380959879 619963443 106167226 73865409 826858024 56062512 437693354 340445108 604619683 791991483 7300264...
output:
7769103153522109 21209520101497866 12453875916706553 21861512525349055 21994844775114551 22606385523748384 4962030058940312 20614777846726216 4514335046749431 20346398113954539 16479975916989640 2806007917483201 19622386582746420 22955087055842971 21041026349491377 24046136537255789 2041470515268697...
result:
ok 200000 lines
Test #45:
score: 0
Accepted
time: 606ms
memory: 153808kb
input:
200000 1000000000 200000 221911326 672598376 586864284 652343839 645072453 477182516 470253244 169559270 913860372 153896545 452982258 356042452 131678734 285479642 780356439 919192461 374130593 89810026 390686444 990599905 300023735 916489417 40995583 613948336 361863393 17299001 909709725 80365886...
output:
3850358894573407 4727815116715378 6494041025937004 4824435980551637 3378697610475978 5909426402365293 5518872599382274 4158124880334301 3937773073272371 9687643834151992 2427228601277127 2243767802218885 2464182590746753 8320457785791601 2372831686710907 7624139791764704 2729257787239080 90363701429...
result:
ok 200000 lines
Test #46:
score: 0
Accepted
time: 688ms
memory: 160912kb
input:
199997 1000000000 200000 418668520 349968181 349972501 413151936 413168716 358529603 413712865 419740996 413260207 413754768 413754409 413644778 352475862 391987463 349972716 1000000000 349968635 376567534 413307389 413513241 392814142 413753730 349967166 349969051 365151841 349973369 413757992 3499...
output:
246430378081337415 289991643186437654 296315729206931331 364169975100364021 192595239991666627 57389957577630585 322772936556813385 154410265195118126 15121202928554667 95942665106074526 29110913867320341 247647043585119923 331278885019774528 399239706543450142 259799041077439947 308782410202237399 ...
result:
ok 200000 lines
Test #47:
score: 0
Accepted
time: 1145ms
memory: 159092kb
input:
199997 1000000000 200000 5099350 2290489 288943 3023893 498119 1980893 61654 4972753 2125310 135980 1090538 2954994 4015300 812572 4645903 3233143 1379788 818444 1534283 4069851 19634 2435868 4145501 16053 5943 3925849 3172608 871962 1005093 1205114 8917 758532 3035834 2817889 545073 3670544 5057079...
output:
234196984676 486350257291 322294896890 216546281167 494216113461 572299792560 489662712294 475722942319 243629568040 429703691047 203546469394 283970977506 247616916213 535967681169 243027652067 472054561070 338167336711 249147033135 288935860327 290760911811 309565528803 513985763532 431591688646 4...
result:
ok 200000 lines
Test #48:
score: 0
Accepted
time: 673ms
memory: 163828kb
input:
200000 1000000000 200000 400973183 400377730 400709896 400180375 400313803 400511962 400371890 400134460 400148639 400269163 400170270 1000000000 400217075 400325397 400194331 1000000000 400130150 1000000000 400102020 400139679 400123734 1000000000 400126747 400222387 1000000000 400122213 400115355 ...
output:
330898574562445672 112499815410130451 292078105105911864 226269792209495968 86667035410318720 173003927946045263 96345981791642245 386925883084229768 201270426486087515 390559064393977652 363775401603363524 316465987026547677 189681741290208846 179522924025315419 231976763836669836 17536211389322141...
result:
ok 200000 lines
Test #49:
score: 0
Accepted
time: 1290ms
memory: 163784kb
input:
200000 1000000000 200000 3104552 3104468 3104522 3104441 3104006 3104418 3104492 3104257 3104338 3103037 3103790 3104124 3104403 3104409 3104324 3104186 3103634 3100765 3102923 3098416 3101925 3103680 3102937 3103140 3103205 3104375 3104227 3097705 3104353 3099751 3104174 3104077 3098358 3103547 310...
output:
299170245832 492089907878 234626220221 479271609338 502550631422 276242675712 568363575475 499894660691 637989402461 528007462738 472851936868 609342882560 603201080952 470943763001 332242018172 266091057439 451790590271 501620901482 570283671029 619943731238 492033377164 607909626590 555558037644 4...
result:
ok 200000 lines
Test #50:
score: 0
Accepted
time: 852ms
memory: 154316kb
input:
199924 1000000000 199984 399869085 398376861 439948274 399733681 398624841 398713237 479735387 399767025 400080369 649078920 399661262 400009677 1000000000 399981396 399790787 398757873 400028368 410098923 400282166 399725262 399857368 398570981 398465638 399994302 400011046 398750814 701394147 4264...
output:
274712263738077387 361957805519428564 312885220894571314 91126316434021637 14632663337398615 288041199082475383 285788012165091014 239444158149519924 228152425395680281 386763034110222318 335523640469294150 231950045342323397 11909732801116553 327243695168307095 227866104753359078 293094204545827505...
result:
ok 199984 lines
Test #51:
score: 0
Accepted
time: 619ms
memory: 154428kb
input:
200000 1000000000 200000 391175458 386460764 381754652 782149047 413042241 391189070 386250325 408504234 450354921 389257952 400953425 400000679 383617987 870067693 407269224 383581360 413227573 382122391 385646739 405208885 412435077 549469669 392037145 387667032 387500501 395760590 408533213 40678...
output:
359574023501711749 189386606118067911 340221522042157239 94695135310902641 194853259519380481 204036382398674152 220150543637394295 247692420482925693 170505194682743836 128701965779923218 221082537626355128 152363458918389004 229636099144301752 212471069198315247 290534107817356008 3837587588639638...
result:
ok 200000 lines
Test #52:
score: 0
Accepted
time: 301ms
memory: 148884kb
input:
200000 1000000000 200000 474717573 399999395 399998209 399998002 400000391 400000384 400000598 400001243 399997532 399998369 400000255 399998545 400000326 522897504 399998475 400000410 400000375 399998364 399998641 399998124 399997405 399997992 399998572 399999371 400000289 400001268 399998034 39999...
output:
173736955036522085 33650951440191764 143730970143276166 99418193510942190 342634198332954072 162502488670705477 375965255476953997 258543590358454738 232061399883523900 261060000771343170 357529029841999653 240058654959790996 204637421229932299 343226944296757095 151951735010708339 23769275557349395...
result:
ok 200000 lines
Test #53:
score: 0
Accepted
time: 1037ms
memory: 154460kb
input:
199982 1000000000 199933 13905 69644 11795 17651 18054 465661 20911 738216 1097153 735181 986430 65838 1015433 420487 80345 2483 157723 6170 3872 169523 310529 772003 317617 957530 10689 50872 725052 351260 406429 905643 29455 787932 727733 156301 827039 801839 271562 84335 74338 96058 461503 110830...
output:
315889687715 274454363440 294262916565 87340375425 267007540685 359869041992 302546759206 324552934313 226536315022 297144155332 494360796272 355456788344 53123205018 270937855399 250406745471 259508383005 461215278318 300738324383 326197147912 306529365019 267905971033 268651306040 272619646060 235...
result:
ok 199933 lines
Test #54:
score: 0
Accepted
time: 773ms
memory: 154552kb
input:
200000 1000000000 200000 3001595 14097 180920 1421096 1780325 345585 6321 536970 108359 1580188 188319 2209073 93991 62691 826278 1406374 2372360 1935896 2941114 1198315 1818930 159407 182164 1372932 1257296 2766581 1294716 1197130 1954695 2410246 229834 2266485 1553788 1983380 994284 250717 583339 ...
output:
464814966079 550459273553 392015576571 330654126238 295524188309 557539614122 499310432985 466739001540 206521426474 486492095002 347320572639 480630888276 303763127639 515800154811 277829449015 491439750254 514105778996 262998042597 477953258405 346983235644 377144239806 469569787980 320557580253 2...
result:
ok 200000 lines
Test #55:
score: 0
Accepted
time: 457ms
memory: 148768kb
input:
200000 1000000000 200000 180082 114229 64689 3671213 168564 3304613 22338 188029 59435 1582099 3442061 4783670 1380330 837820 4808200 64087 125886 480033 18218 3362487 4919646 2317099 146322 34703 161950 1209001 1370897 3727366 291020 4251841 3045276 830451 309 3555827 288899 4096315 1145583 3630161...
output:
470985272633 330577001589 439814644058 523567895118 501048366869 462793156984 291316709009 404699099167 290256852644 444960749007 473443352397 538540471582 643148473320 273919681872 601471298829 498808821230 571596269149 377997366417 384048397221 473618982159 527591322785 251088873050 454153652833 4...
result:
ok 200000 lines
Test #56:
score: 0
Accepted
time: 8ms
memory: 121220kb
input:
1 2 5 1000000000 1 1 1 2 1 2 1 1 1 1
output:
0 1000000000 1000000000 0 0
result:
ok 5 lines
Test #57:
score: 0
Accepted
time: 4ms
memory: 122504kb
input:
2 1 5 2 1 1 2 1000000000000 1 1 1 2 1 1 1 1 1 2
output:
0 1000000000000 0 0 1000000000000
result:
ok 5 lines
Test #58:
score: 0
Accepted
time: 783ms
memory: 155572kb
input:
200000 4000000 200000 469534105 869657262 201026406 706247703 720363334 591393274 140527583 403309685 669391268 962180948 533915565 370916928 278461532 572910588 36045110 106609732 314193846 638246398 749887226 95860789 609990162 263858083 933984169 92866433 774165117 800604654 471471901 384849200 9...
output:
1423533148858611 1203199106273073 65596428936959 1469120764498552 1338293611070646 1031513116329584 1293493771712425 1449296607273261 1448987449112301 1448657128680465 1448482174566858 1279397039368897 1449767211059881 857407952795972 1138358455373900 1449579740661381 1360981514512919 96162444990027...
result:
ok 200000 lines
Test #59:
score: 0
Accepted
time: 747ms
memory: 155600kb
input:
200000 1000000000 200000 3695933 725812 3938862 3188795 74871 179361 892126 899932 2952206 1461698 674172 2140411 3124478 253567 1930733 1468200 844171 3820729 3146995 2143636 3012500 3860711 1978473 458453 1011065 3915797 2489264 581391 3663430 200944 463051 2789062 329754 3391992 1666664 1278446 3...
output:
1313893005299891 1241413179669075 1013214888095897 1283956382437075 832938541171640 1357016581395659 1358632237670655 1358575371105735 1359617242208535 1358550490017855 1262000024359038 1090246621403288 1365726941260351 1070531999758396 1247397876139791 1294791538934294 931852209639129 1358682897483...
result:
ok 200000 lines
Test #60:
score: 0
Accepted
time: 1117ms
memory: 155216kb
input:
200000 1000000000 200000 1000000000 395785681 450569981 397435194 399243043 815631194 396368986 396009218 395184318 399082057 396553759 395139833 405819304 397314248 404595065 396486584 396139088 398990743 397510485 561967645 408268414 396500176 395757782 456603560 396336452 399624664 396449945 3959...
output:
109920129587885069 378225816640797819 309690844924907845 267339736788532370 372175904770256958 321135232766545507 232563027043320134 124882843097505896 115857700588107460 202847102004389723 389602100695363841 235317792421863006 253135733788837109 220301266029980272 169917572575901836 214668686787005...
result:
ok 200000 lines
Test #61:
score: 0
Accepted
time: 1452ms
memory: 155520kb
input:
200000 1000000000 200000 1867594 524322 3615 25303 1538215 1040257 1623469 84359 1503219 419070 1873718 873101 203084 1842101 1034729 598281 1086715 1851042 1126586 240305 111153 1411689 755343 23669 1982825 1608454 2068771 2085317 1086469 19627 30122 1623595 138403 33439 1979692 1136830 173176 1415...
output:
306225753801 342005544451 436459567316 236781181877 341005923055 438745980019 330732109809 239627724290 562373111121 467513530464 239225732828 326333872737 326471417616 429675583322 552828882509 239263092986 288718695356 245227283983 471568113901 241072755476 241360488328 309136881480 242266843083 2...
result:
ok 200000 lines
Test #62:
score: 0
Accepted
time: 1335ms
memory: 156600kb
input:
200000 1000000000 200000 941812 82062 38722 678737 68338 1072195 141897 141638 1002771 780921 137477 673465 918996 649333 406005 726096 496011 796418 346152 733114 890963 1057424 367441 343348 18182 83852 84060 786683 504660 44953 769252 734380 460070 272021 934209 71402 748582 323154 298122 7832 15...
output:
126436853796 465180591754 369107820231 281078670236 345259813302 494359911875 244336591685 484282259162 243752267165 460503945863 473839717345 439525600179 243099218281 505218592257 363750198100 244895817789 374199391493 465134123100 207985506641 513109340343 498612704121 213872806786 460528982772 2...
result:
ok 200000 lines
Subtask #7:
score: 0
Skipped
Dependency #1:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%