QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303551#4924. 蜘蛛爬树zyc07041931 1452ms176220kbC++148.1kb2024-01-12 18:12:402024-01-12 18:12:40

Judging History

你现在查看的是最新测评结果

  • [2024-01-12 18:12:40]
  • 评测
  • 测评结果:31
  • 用时:1452ms
  • 内存:176220kb
  • [2024-01-12 18:12:40]
  • 提交

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%