QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334196#6111. Two PathsFISHER_WA 1273ms137148kbC++208.2kb2024-02-21 13:57:072024-02-21 13:57:08

Judging History

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

  • [2024-02-21 13:57:08]
  • 评测
  • 测评结果:WA
  • 用时:1273ms
  • 内存:137148kb
  • [2024-02-21 13:57:07]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e15;
const int N = 2e5;
inline int read() {
    int s = 0,f = 1;char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
    return s*f;
}
/*
1:u,v在同一子树
此时,其中一个可以往上走到某个直径端点,另一个走到lca往下一个儿子的子树直径的一个端点
2:u,v在不同子树
此时,第一类:分别走到离自己近的直径端点
第二类:往中间走,各自找到一个位置进入子树。
贡献如何统计?
假设选了 j,k(u<j<k<v)
贡献为:(d[u]+(s[j]-s[u])+mxd[j])A+(d[v]+(s[v]-s[k])+mxd[k])B
求max{(s[j]+mxd[j])A+(-s[k]+mxd[k])B},j<k 
*/
int n,q,head[N + 10],cnt;
struct edge {
    int v,w,nxt;
}ed[N * 2 + 10];
void add(int u,int v,int w) {
    ed[++cnt] = {v,w,head[u]};
    head[u] = cnt;
}
int dep[N + 10],fa[N + 10],sz[N + 10],son[N + 10],top[N + 10],id[N + 10],tot,rnk[N + 10];
int dd[N + 10];
int mx,Id,rt1,rt2,fl,ct,st[N + 10],ind[N + 10];
void dfs(int x,int f) {
    fa[x] = f, dep[x] = dep[f] + 1, sz[x] = 1;
    for (int i = head[x];i;i = ed[i].nxt) {
        int v = ed[i].v;
        if (v == f || ind[v]) continue;
        dd[v] = dd[x] + ed[i].w;
        dfs(v,x);
        sz[x] += sz[v];
        if (sz[son[x]] < sz[v]) son[x] = v;
    }
}
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 dep[x] < dep[y] ? x : y;
}
int dis(int x,int y) {
    int lca = LCA(x,y);
    return dd[x] + dd[y] - 2 * dd[lca];
}
struct dia {
    int x,y,d;
    bool operator < (const dia &a) const {
        return d < a.d;
    }
    friend dia operator + (dia x,dia y) {
        return max({x,y,{x.x,y.x,dis(x.x,y.x)},{x.x,y.y,dis(x.x,y.y)},{x.y,y.x,dis(x.y,y.x)},{x.y,y.y,dis(x.y,y.y)}});
    }
}di[N + 10];
void dfs2(int x,int tp) {
    top[x] = tp, id[x] = ++tot, rnk[tot] = x;
    if (!son[x]) return;
    dfs2(son[x],tp);
    for (int i = head[x];i;i = ed[i].nxt) {
        int v = ed[i].v;
        if (v == fa[x] || v == son[x] || ind[v]) continue;
        dfs2(v,v);
    }
}
void dfs3(int x,int fa,int d) {
    if (d > mx) mx = d, Id = x;
    for (int i = head[x];i;i = ed[i].nxt) {
        int v = ed[i].v;
        if (v != fa) dfs3(v,x,d + ed[i].w);
    }
}
void dfs4(int x,int fa,int y) {
    if (fl) return;
    st[++ct] = x;ind[x] = 1;
    if (x == y) {
        fl = 1;
        return;
    }
    for (int i = head[x];i;i = ed[i].nxt) {
        int v = ed[i].v;
        if (v != fa) dfs4(v,x,y);
    }
    if (!fl) ct --, ind[x] = 0;
}
int getk(int x,int k) {
    if (k < 0) return -1;
    while (k >= id[x] - id[top[x]] + 1) {
        k -= id[x] - id[top[x]] + 1;
        x = fa[top[x]];
    }
    return rnk[id[x] - k];
}
int to[N + 10],s[N + 10],mxd[N + 10];
void dfs5(int x,int rt) {
    di[x] = {x,x,0};
    to[x] = rt;
    mxd[rt] = max(mxd[rt],dd[x]);
    for (int i = head[x];i;i = ed[i].nxt) {
        int v = ed[i].v;
        if (v == fa[x] || ind[v]) continue;
        dfs5(v,rt);
        di[x] = di[x] + di[v];
    }
}
map<pair<int,int>,int> mp;
int pre[N + 10],suf[N + 10];
int tp;
struct vec {
    ll x,y;
    vec(){}
    vec(ll X,ll Y) {x = X, y = Y;}
    vec operator + (vec a) {return vec(x+a.x,y+a.y);}
    vec operator - (vec a) {return vec(x-a.x,y-a.y);}
    vec operator * (double a) {return vec(x*a,y*a);}
    friend ll cross(vec x,vec y) {return 1ll * x.x * y.y - 1ll * x.y * y.x;}
}a[N + 10],b[N + 10];
int cmp(vec x,vec y) {
    return x.x == y.x ? x.y < y.y : x.x < y.x;
}
ll calc(vec x,vec y,vec k) {
    return cross(y-x,k-x);
}
struct Seg {
    int l,r;
    vector<vec> vc;
}t[N * 4 + 10];
void build(int x,int l,int r) {
    t[x].l = l, t[x].r = r;
    for (int i = l;i <= r;i ++ ) b[i] = a[i];
    sort(b + l + 1,b + r + 1,cmp);
    for (int i = l;i <= r;i ++ ) {
        while (t[x].vc.size() > 1 && calc(t[x].vc[t[x].vc.size() - 2],t[x].vc.back(),b[i]) >= 0) t[x].vc.pop_back();
        t[x].vc.push_back(b[i]);
    }
    t[x].vc.push_back({0,0});
    if (l == r) return;
    int mid = l + r >> 1;
    build(x<<1,l,mid), build(x<<1|1,mid + 1,r);
}
ll query(int x,int l,int r,ll A,ll B,int u,int v) {
    if (l > r) return 0;
    if (t[x].l >= l && r >= t[x].r) {
        int l = 0,r = t[x].vc.size() - 2;
        while (l < r) {
            int mid = l + r >> 1;
            if (t[x].vc[mid].y * B + t[x].vc[mid].x * A >= t[x].vc[mid + 1].y * B + t[x].vc[mid + 1].x * A) r = mid;
            else l = mid + 1;
        }
        return A * (dd[u] - s[to[u]]) + B * (dd[v] + s[to[v]]) + t[x].vc[l].y * B + t[x].vc[l].x * A;
    }
    int mid = t[x].l + t[x].r >> 1;
    ll res = 0;
    if (mid >= l) res = query(x<<1,l,r,A,B,u,v);
    if (mid < r) res = max(res,query(x<<1|1,l,r,A,B,u,v));
    return res;
}
signed main() {
    n = read(), q = read();
    for (int i = 1;i < n;i ++ ) {
        int u = read(),v = read(),w = read();
        add(u,v,w), add(v,u,w);
        mp[{u,v}] = mp[{v,u}] = w;
    }
    dfs3(1,0,0);mx = 0, rt1 = Id, dfs3(rt1,0,0);
    dfs4(rt1,0,Id);
//  for (int i = 1;i <= ct;i ++ ) cout << st[i] << ' ';puts("");
    for (int i = 1;i <= ct;i ++ ) {
//      cout << "!!" << i << ' ' << s[i] << endl;
        dfs(st[i],0), dfs2(st[i],st[i]);
        dfs5(st[i],i);
        if (i > 1) s[i] = s[i - 1] + mp[{st[i - 1],st[i]}];
        pre[i] = max(pre[i - 1],s[i] + mxd[i]);
    }
//  cout << rt1 << ' ' << Id << endl;
    suf[ct + 1] = -inf;
    for (int i = ct;i;i -- ) suf[i] = max(suf[i + 1],-s[i] + mxd[i]), a[i] = {s[i] + mxd[i],suf[i + 1]};
    build(1,1,ct);
    while (q -- ) {
        int u = read(),v = read();
        ll A = read(),B = read();
        if (to[u] > to[v]) swap(u,v), swap(A,B);
        ll ans = 0;
        if (to[u] == to[v]) {
            int lca = LCA(u,v);
            int uk = getk(u,dep[u] - dep[lca] - 1),vk = getk(v,dep[v] - dep[lca] - 1);
            if (uk != -1) ans = max(ans,B * (dd[v] + max(s[ct] - s[to[v]],s[to[v]])) + A * max(dis(u,di[uk].x),dis(u,di[uk].y)));
            if (vk != -1) ans = max(ans,A * (dd[u] + max(s[ct] - s[to[v]],s[to[v]])) + B * max(dis(v,di[vk].x),dis(v,di[vk].y)));
            printf("%lld\n",ans);
        }
        else {
            ans = max(ans,B * (dd[v] + s[ct] - s[to[v]]) + A * (dd[u] + s[to[u]]));
            ans = max(ans,B * (dd[v] + s[ct] - s[to[v]]) + A * (dd[u] - s[to[u]] + pre[to[v] - 1]));
            ans = max(ans,B * (dd[v] + s[to[v]] + suf[to[u] + 1]) + A * (dd[u] + s[to[u]]));
//          cout << "ans:" << ans << endl;
            if (!ind[u]) {
                int uk = getk(u,dep[u] - dep[st[to[u]]] - 1);
                ans = max(ans,B * (dd[v] + s[to[v]]) + A * (max(dis(u,di[uk].x),dis(u,di[uk].y))));
            }
            if (!ind[v]) {
                int vk = getk(v,dep[v] - dep[st[to[v]]] - 1);
                ans = max(ans,A * (dd[u] + s[ct] - s[to[u]]) + B * (max(dis(v,di[vk].x),dis(v,di[vk].y))));
            }
            /*
            x[i]=s[i]+mxd[i]
            y[i]=suf[i+1]
            */
//          int l = to[u] + 1,r = to[v] - 1,fl1 = 0;
//          for (int i = l;i <= r;i ++ ) vv[i] = val(i,A,B), mx =
//          double k = -A * 1.0 / B;
//          while (l < r) {
//              int mid = l + r >> 1;
//              if (mid == to[v] - 1) {
//                  l = mid;
//                  break;
//              }
//              if (val(mid,A,B) == val(mid + 1,A,B)) fl1 ? r = mid : l = mid + 1, fl1 = 0;
//              else if (val(mid,A,B) > val(mid + 1,A,B)) r = mid, fl1 = 1;
//              else l = mid + 1, fl1 = 0;
//          }
            ans = max(ans,query(1,to[u] + 1,to[v] - 1,A,B,u,v));
//          ans = max(ans,A * (dd[u] + s[l] - s[to[u]] + mxd[l]) + B * (dd[v] + s[to[v]] + suf[l + 1]));
//          for (int i = to[u] + 1;i < to[v];i ++ )
//              ans = max(ans,A * (dd[u] + s[i] - s[to[u]] + mxd[i]) + B * (dd[v] + s[to[v]] + suf[i + 1]));
            printf("%lld\n",ans);
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 35100kb

input:

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

output:

18
32
18
160

result:

ok 4 number(s): "18 32 18 160"

Test #2:

score: 0
Accepted
time: 3ms
memory: 35064kb

input:

2 1
1 2 1
1 2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 35068kb

input:

2 10
1 2 2
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 3 1
1 2 3 2
1 2 3 3
1 2 2 3
1 2 1 3

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 68ms
memory: 35136kb

input:

10 500000
4 5 576
5 8 218
1 10 678
1 9 2540
7 8 2023
2 7 5510
2 9 8454
4 6 22
3 9 5248
2 5 35782 82142
1 2 95412 85188
4 5 82466 22193
3 6 22169 67901
4 10 67229 30987
1 10 68282 17858
1 8 53726 3246
5 8 13913 74110
2 8 30052 7204
1 4 95255 48216
2 5 41392 98997
3 8 8435 5947
1 5 22067 21610
7 9 343...

output:

674365186
1454303268
477920681
1359445921
1501996827
1320778726
889342640
1582045824
426346196
1792561801
789005461
166905972
478560756
71705653
343648830
901237204
420263788
1710700661
309792440
335240094
1852278021
1679904905
1055408048
1644275016
563316675
602184744
873340490
815015664
1356022267...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 100ms
memory: 35108kb

input:

100 500000
4 63 6394
57 91 2108
5 52 9292
6 63 3151
52 62 1006
13 19 8138
42 59 6102
3 95 275
36 80 8426
20 84 7879
32 100 4423
71 89 9590
55 98 240
46 100 7470
70 92 7417
43 54 6092
24 41 230
93 94 6591
8 92 2558
34 63 7534
4 36 5620
17 93 987
35 96 1288
42 68 6280
72 89 9818
43 57 8266
26 62 2431
...

output:

30730511688
35868047826
94569561805
103860674856
108734641138
103921529851
151172279864
108994447520
79859941598
90637244010
113651189677
26614889256
54138181416
163935808262
43257729984
101945300646
27547811269
67543514171
84292164869
59484837480
117300068794
77146438694
27400485192
55424042658
628...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 681ms
memory: 91696kb

input:

200000 500000
83239 106513 1257
142726 196994 1263
95614 142588 7488
88575 193932 8123
31396 180633 1564
37559 131657 927
143893 157390 740
117889 182920 7831
103309 142289 6864
15478 36228 2717
5896 6815 5902
42275 184396 2646
21903 63571 8966
23873 42450 2721
36540 46154 9467
155293 161123 8588
54...

output:

5966882576104305
7271792958583645
8570461339781342
9614114352538144
6712681170527500
9409581586879995
6304678086998919
6559831613756394
4016495625693024
4381351843519688
4971908463803118
8759545709797016
11418325924391126
8912046248703475
10780907424911508
3112723787504739
9395431732704804
851233289...

result:

ok 500000 numbers

Test #7:

score: 0
Accepted
time: 66ms
memory: 35088kb

input:

10 500000
7 8 6474
3 4 6652
4 5 5193
6 9 457
5 9 3937
1 7 7261
2 5 6472
6 8 6967
3 10 8997
2 9 77462 28703
3 7 31026 16732
2 6 39340 36431
6 9 95641 333
4 8 17377 97247
2 4 20769 98147
4 6 425 42124
4 8 53119 54974
2 4 49307 3731
1 7 13417 95608
7 8 36330 40656
6 10 16594 36336
1 6 47819 1121
1 3 93...

output:

2723123845
841480408
1828727322
1988211389
2006138424
2972774483
878701873
1811610573
1614909795
3697830616
1573037298
1336010492
685083521
3657916506
2557058802
3370810317
3011684921
862077669
2124928512
3326043566
1360831395
1603107540
3131147303
1037179764
1973141216
1587191713
747094784
36277104...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 87ms
memory: 35136kb

input:

100 500000
40 72 2893
46 57 7594
13 90 4014
32 59 8870
4 81 4432
59 94 8856
59 96 4895
96 100 9950
32 80 8362
5 89 1777
36 69 2134
24 62 9978
21 65 3506
49 61 6056
33 48 5740
1 30 4143
30 60 8914
60 70 4900
66 93 6395
10 68 1687
10 95 2472
4 20 3135
2 17 9637
56 78 4429
20 27 2053
52 89 6906
27 39 9...

output:

106913710770
4495733708
102758976134
80160799892
76732267750
47039029473
72520507589
73042063332
73155659164
70949908024
18019999665
55814535350
72254712051
121025392740
66270956091
135577152247
39206666175
97754289402
83622700164
89895046420
147890155522
62926235281
108657350392
100238158900
814086...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 709ms
memory: 91712kb

input:

200000 500000
72622 96340 7225
16757 66347 2999
101297 187932 6437
49037 154632 460
124025 196592 9940
153072 170123 1421
34394 199313 4817
32364 32518 5106
88700 199062 8686
31819 36499 9765
52871 159318 6576
1498 113000 6088
87532 137708 9913
18424 42545 9372
10501 33545 5958
23767 170025 2704
187...

output:

14850031235173232
6999821359673356
13994322220418811
15658897860429808
5566180270698198
7768919631255131
7795054483438192
7419776394069074
12641505965465227
7472188388977804
15268455327661860
10901394489199617
8199280990426768
12441824458056512
5059765147523162
8301785128173369
6921399963160754
9272...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 76ms
memory: 35148kb

input:

10 500000
7 8 6564
4 8 6189
3 9 5516
2 4 8374
2 9 4364
7 10 7523
6 8 9898
5 8 7016
1 5 2345
5 8 51845 42560
4 5 55887 98340
3 8 49610 54530
9 10 22945 35062
3 8 3458 95253
3 6 23153 11481
1 8 34851 37986
5 9 87362 27198
1 7 55997 43106
1 7 75611 27271
7 8 71599 78148
6 7 34117 75458
2 4 79390 55048
...

output:

1161870605
3095430318
1673745050
1133235480
1802853531
892085090
1010217393
2190048410
2217209026
2761113977
2448810841
2339726206
1900526448
2923869030
1282299167
2882083522
2590862660
2125646342
2738520864
1608180381
1666730547
2125172192
2345809770
1603963890
3685256440
2391830675
183542487
93557...

result:

ok 500000 numbers

Test #11:

score: 0
Accepted
time: 89ms
memory: 35184kb

input:

100 500000
64 80 6288
35 50 3079
47 52 1840
5 69 4588
3 14 5154
76 80 5382
35 60 9496
19 61 9625
71 73 9786
7 46 9867
5 15 9846
14 57 7663
39 52 9476
21 38 3153
44 63 1358
60 67 4899
56 59 302
8 52 104
50 56 2937
28 72 8543
85 91 7835
16 87 5283
29 77 3795
11 84 6769
49 65 1585
45 51 1354
2 89 9853
...

output:

72202925787
97514852513
56756195638
37288713475
35676803180
90017144414
38927158215
28601206274
14400684154
45932515989
77207561276
59432631660
70376380240
78182150824
76907451131
97790656742
61036431338
66756945882
44962902462
95491099215
84137846038
57887416052
58421189377
45768814245
47300757994
...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 706ms
memory: 91772kb

input:

200000 500000
84618 98845 7176
107087 196559 4404
173709 192096 4717
122383 132949 1263
13177 34882 5439
139807 160157 1421
45167 91345 9766
107962 187717 2148
66125 151170 6686
63358 86085 5420
92294 134701 5058
113293 149067 2818
52824 164065 9708
44586 64319 6527
52176 147205 1116
36120 153708 18...

output:

10077660798661166
6673502274389958
12939177208895010
9047200007665110
6573554974664500
5242597508990838
13676616292679150
9704815634833183
11561184450694770
12472403863791083
13122447381660824
13320490331795583
8658969745868196
8796014087160251
13063721599988841
12566284718749275
7973072528332602
11...

result:

ok 500000 numbers

Test #13:

score: 0
Accepted
time: 66ms
memory: 35072kb

input:

10 500000
5 10 9359
6 8 2622
3 4 32
1 5 6291
2 5 4790
6 7 9273
5 7 7916
2 3 1256
7 9 6094
1 4 93524 56417
1 4 72235 21165
1 8 59881 96821
3 7 60649 69792
3 7 40702 86345
2 7 89678 55741
3 7 83505 90656
9 10 91223 25352
6 10 12287 11104
5 8 94433 78823
4 6 19397 21614
2 6 56138 89726
3 7 87392 7152
2...

output:

2513828544
1912738490
2824268570
1764473685
1654088085
1931893217
2364747645
2037769347
362591929
2301745394
631573827
2454351592
1431346800
1917618468
112297763
185018940
1653764936
1250254372
1568465383
1292309244
236168002
506864435
425491147
2028002330
476710384
1808277470
2247989250
1318111291
...

result:

ok 500000 numbers

Test #14:

score: 0
Accepted
time: 102ms
memory: 35184kb

input:

100 500000
8 10 4275
5 60 2756
55 71 6562
46 53 306
40 85 8980
24 97 1909
59 90 8289
58 77 9299
38 74 9722
5 95 9173
34 42 7558
35 92 8051
78 86 5446
29 63 4443
72 78 3872
26 100 246
35 50 203
73 74 2605
53 74 6774
66 81 6888
39 66 4686
31 62 4727
3 92 9440
71 88 4918
18 90 9628
22 46 9995
28 49 991...

output:

65913039086
86901503285
145182328228
51391603893
107334514650
33026739520
141561395797
94885846572
85557851805
95450858526
43327973728
76933550118
105576354578
116690159952
127214406241
57156892577
92243211803
2929303556
60914681674
87520089774
88616664175
89811058923
60767857476
39044073040
6597593...

result:

ok 500000 numbers

Test #15:

score: 0
Accepted
time: 748ms
memory: 91820kb

input:

200000 500000
48263 193405 8782
39826 138335 6086
43411 47049 42
32460 100163 6561
110839 195838 6052
5325 169299 7212
2594 89322 851
46973 138509 8277
45626 176835 6893
94589 172557 9834
46014 69648 1541
10815 31117 7070
123771 141531 2871
72939 179823 4185
68124 69369 7576
127353 144997 9295
96779...

output:

4813047735928155
13563121456000208
10623977740697384
12368325537868986
9906634169705396
15509065513494903
5103499979323596
12246478270010336
14933318539416384
8682385540396731
6020406730020679
14413092183185878
12398399473755534
14259938583507292
11726545588336542
12617036028393990
11053303327631314...

result:

ok 500000 numbers

Test #16:

score: 0
Accepted
time: 70ms
memory: 35076kb

input:

10 500000
3 7 9449
3 5 2159
5 8 355
1 3 1104
6 9 6705
9 10 9535
4 7 5934
4 6 8201
2 4 9843
1 9 92099 2978
2 10 29800 2773
3 9 45959 6408
8 10 55249 4522
1 8 98109 69741
1 7 56836 13930
1 4 7749 81274
3 6 67170 72637
3 4 39522 19991
3 8 28045 8334
1 3 73971 33646
3 8 24965 37029
2 7 24474 60167
3 4 8...

output:

2453361900
871685520
1220462014
1812332947
4040163207
628756398
2068193031
2874055300
862043409
1119822650
1339918304
1007351455
1827572625
1163734879
2383959500
1900098890
2455446271
1823237724
2457600854
2669165980
2242954420
2886332020
2097531384
666029210
2068152260
875855713
3015757786
17857956...

result:

ok 500000 numbers

Test #17:

score: 0
Accepted
time: 117ms
memory: 35176kb

input:

100 500000
14 76 774
6 50 8242
20 77 1284
54 69 3321
7 46 2405
56 64 8435
29 67 7083
19 81 2078
14 95 1146
21 91 7263
17 83 6757
5 43 8439
51 88 8712
15 85 5732
34 89 2194
4 26 1001
50 91 8887
3 37 5105
48 81 1827
42 58 1040
61 79 4242
6 82 6875
44 62 3598
59 91 9962
25 91 4568
59 73 8635
76 100 997...

output:

116400494286
104580113985
68880117122
131948244233
35343773131
100666540698
75158851568
89717230196
104502389946
48973081722
100478141976
91980290003
137115094714
93668643240
107190886884
99570436976
109341640400
113119225372
64886734716
49555552176
103942689145
79245699399
96260733612
93079934826
1...

result:

ok 500000 numbers

Test #18:

score: 0
Accepted
time: 721ms
memory: 91744kb

input:

200000 500000
131798 169313 5103
10660 167741 8275
71369 177082 7071
94023 175057 6285
5236 62128 4118
45145 49844 5960
5469 27531 1940
91347 139404 2938
81422 163356 909
143033 192772 3189
79340 148691 8720
80447 94182 3029
156490 164075 3647
67391 99673 841
19307 109516 858
52393 130048 5572
11053...

output:

10800964533361095
13397792616011778
2840433935282426
4089862708527832
5612515473124553
11282891088637211
14247727524719144
10608965275092284
6469991183666541
14868049842352340
6737187884943531
8881942760307495
6038742155446525
4524630271319190
6043319166641563
5691043644442530
6839751030234923
14050...

result:

ok 500000 numbers

Test #19:

score: 0
Accepted
time: 64ms
memory: 35076kb

input:

10 500000
4 10 9539
2 7 8593
3 10 7974
6 9 9021
2 8 4427
1 7 7094
3 7 6656
5 9 8250
3 6 7783
6 10 66482 73731
2 3 78853 92894
7 9 56229 24507
2 7 25657 39252
3 9 88219 10034
6 10 91291 72118
6 9 68635 77327
2 5 92335 48990
2 6 28564 34863
3 7 64020 60300
1 3 81195 77522
5 10 13705 14899
2 5 74356 64...

output:

3186872772
3564333287
1580076348
1358264459
1826313758
3570749561
2522596215
3871185560
1537932641
2389063080
3575392418
755146211
3924253368
2118317205
2671630920
2305723692
3392396114
2653834329
2323642550
2126838922
2819453713
2894045195
2848017800
2236762853
4134443688
1576405524
3747787953
1784...

result:

ok 500000 numbers

Test #20:

score: 0
Accepted
time: 103ms
memory: 35196kb

input:

100 500000
21 87 4169
33 37 3727
75 84 9110
54 63 1743
48 91 8935
5 22 4961
1 90 1684
23 60 1753
89 93 1083
42 88 1162
50 56 4469
49 70 6123
30 82 4683
23 77 7021
12 24 517
16 33 6349
78 92 275
53 74 7606
22 53 5665
69 72 2089
48 82 6901
6 13 6319
12 97 9243
4 15 8111
7 64 9908
21 34 7276
45 71 3146...

output:

110748389784
38264562297
43359546636
101911021064
30699213294
36015252942
66923406949
122805090233
79042845551
85174670294
76465411077
111600779360
56770476856
124648390450
55383052877
89724504242
104478388504
75640827746
155849821685
132186971658
99149089195
96175712205
92808752603
51408413125
1531...

result:

ok 500000 numbers

Test #21:

score: 0
Accepted
time: 752ms
memory: 91856kb

input:

200000 500000
85651 116999 6112
158097 171696 7424
81082 114242 60
37965 54899 6
125494 187147 2082
49480 63274 3900
35086 198565 7888
20283 122198 9709
784 61133 2439
71605 185908 7979
95753 169217 3965
62954 133637 9554
3981 167663 7799
33102 34663 8954
130446 146696 4934
8205 166566 7149
58213 58...

output:

6629318792107142
10044113522610660
2330988015274776
12278123707454910
12875452078148204
11884913875794177
13377361131534638
4162637141844698
10395433513479830
1656706940234251
9416321342660328
4009752871445568
8946741333314748
10764269715844342
5609227805988978
14947691905102305
15036214604008772
10...

result:

ok 500000 numbers

Test #22:

score: 0
Accepted
time: 62ms
memory: 35168kb

input:

10 500000
1 4 2333
5 9 8130
5 7 5193
1 2 6938
3 6 6342
4 8 8844
8 9 4674
3 4 5195
5 10 4236
6 10 8162 87588
3 10 36418 7206
8 10 42308 34094
9 10 69914 24030
4 7 25745 6115
7 10 90829 5614
2 5 5274 43016
1 2 93991 3173
5 10 76358 24253
1 9 81231 90412
7 10 64509 90419
4 5 39855 74709
4 10 85353 1435...

output:

3130919544
1166687048
1283885752
1978274140
666383580
3485835362
1464076972
2742093434
2533940230
2828853338
3383569399
1416381171
2290959873
720247712
1788311442
888393556
671638500
1346955142
943494291
3047948234
2223756945
1642791852
2448163256
1258738266
1540328357
1707714964
2506707831
12724457...

result:

ok 500000 numbers

Test #23:

score: 0
Accepted
time: 121ms
memory: 35120kb

input:

100 500000
30 89 2155
48 65 1916
32 81 3833
2 79 4757
22 60 6953
19 34 1487
16 25 3181
54 82 8724
50 73 2507
72 90 9252
8 77 2181
35 45 6511
21 72 7949
41 79 5607
34 65 8839
21 31 7104
14 49 176
40 80 5914
30 40 2206
40 93 6241
50 57 6456
46 49 5763
50 91 3400
6 78 6259
52 67 2143
33 35 5916
39 63 5...

output:

32912262307
139343527824
44901405068
118159532620
88397372490
110052683328
119328576491
9277212971
123574233705
27991577125
143889082627
173111063353
98995218279
143744963340
102148798266
108724227526
172617870186
66324246022
143879313167
89526963368
118357400256
113714636722
91983601092
16096044184...

result:

ok 500000 numbers

Test #24:

score: 0
Accepted
time: 775ms
memory: 91796kb

input:

200000 500000
70716 167838 2768
12842 140231 3468
95053 173664 1745
114564 160388 1549
169509 189258 5106
89692 155019 4514
115225 171897 6091
87097 110604 1176
89940 117417 2300
86549 197732 4537
12343 133030 5206
88716 197689 6413
85288 157124 4246
46005 124694 719
119999 176784 4897
57160 90184 7...

output:

12732832828062653
9211037791337106
5237768669844932
9023251773903405
8858519509171100
13939771675148235
2699313248449214
7720785879667220
13976414809780410
11491808564740729
8274430160134475
10647944661154060
10637105504452602
9992561160987843
12646401358321221
9426845067847364
13918444902412404
117...

result:

ok 500000 numbers

Test #25:

score: 0
Accepted
time: 70ms
memory: 35148kb

input:

10 500000
4 5 8232
2 8 4563
5 8 2812
2 7 4856
1 5 6768
3 10 6402
2 6 5397
2 3 9435
2 9 7984
3 4 82545 1445
1 4 28575 97326
4 7 19874 43682
1 10 57962 32903
7 8 78841 99132
2 5 17095 64304
7 9 15073 63528
4 10 48518 23005
4 8 53929 12059
5 6 9970 10660
3 10 68509 2443
4 6 33337 29210
2 9 9641 27724
3...

output:

1946246010
3060318744
1202021626
1653212363
2726270621
800084043
1513300488
1291866148
1054938600
308427480
1715602378
1120300140
152684517
1331850486
1080470856
992378094
2285506415
1421551796
613398904
593742225
303233578
3116125396
1252975929
1144870791
2793236600
2612217360
868606320
1956713836
...

result:

ok 500000 numbers

Test #26:

score: 0
Accepted
time: 104ms
memory: 35264kb

input:

100 500000
46 80 2846
6 32 8889
13 40 1659
5 70 475
20 39 7675
26 68 718
25 85 9270
33 44 4206
33 91 2443
17 27 3150
52 54 9892
36 44 4195
2 96 6623
4 22 2704
4 47 8649
23 100 2451
30 37 8860
18 22 8415
29 77 1851
49 55 4586
36 78 9115
23 53 3719
41 85 1750
24 37 8600
48 96 4379
38 63 4557
40 90 568...

output:

113751532017
80123268206
87262423810
137924584380
12800009202
92234031684
58589655165
78344066172
58556856157
48696946584
104850617405
108932596632
17183906241
121368553624
90729404336
43840759604
85075307140
85184463782
24672530760
43602676780
84931463370
61920440394
54949716012
77486651814
5884819...

result:

ok 500000 numbers

Test #27:

score: 0
Accepted
time: 706ms
memory: 91808kb

input:

200000 500000
89413 191901 8274
41004 66726 2629
67729 182199 5599
31500 34542 4398
117299 150081 8774
60011 67816 294
10880 67932 9348
33260 101496 5210
151825 190505 8648
20718 137357 1552
42327 104476 6705
112606 130339 9915
83218 187258 9013
40136 186203 5580
166737 188199 2516
59847 196235 8764...

output:

13470360035139118
15627984620842116
6909370776351859
8565758903929875
1737990841654072
11391139854962264
9886630099101457
16257953272665298
15030575954097100
10134173407874800
7075652323089936
3671195129356384
6042485688632407
8079271696016708
11979823162045712
13114450214675068
8098647102818376
130...

result:

ok 500000 numbers

Test #28:

score: 0
Accepted
time: 61ms
memory: 35140kb

input:

10 500000
1 10 5618
2 9 6804
6 9 31
3 9 2773
7 9 1386
1 7 856
2 5 6119
3 4 2188
1 8 5925
2 6 24224 48006
5 9 77628 11639
4 10 38657 94485
7 9 61074 337
5 6 36247 15232
1 8 51550 22492
3 6 78227 25180
4 8 31900 94974
1 10 25323 26620
1 8 27360 88306
6 10 19483 27773
5 6 80003 18945
8 9 6083 78310
5 7...

output:

541779844
570061445
2048263271
418497845
764449230
781755750
1227850992
2072798860
384023295
414914400
577206259
1687263270
1082216199
437861970
819779180
1478754268
721540744
1337824010
1097899253
1253298460
597971682
1022829994
1449053412
1266804248
2132569267
1903570104
762936815
1006646790
19210...

result:

ok 500000 numbers

Test #29:

score: 0
Accepted
time: 110ms
memory: 35264kb

input:

100 500000
47 48 2049
47 85 4375
47 95 6381
13 77 6194
13 42 6909
2 24 4540
36 94 8063
20 98 6585
3 78 9275
50 54 1240
65 76 4900
59 67 4584
40 56 9889
72 100 3993
32 59 9675
71 99 3207
3 21 248
39 85 915
15 77 5688
37 75 1443
22 51 8671
8 14 5868
36 81 3203
57 87 6748
62 83 2422
17 21 9005
2 43 631...

output:

63285961413
32106790163
81034137362
69774212050
64874364310
33037534269
49801134488
92236309048
103461371576
76807213638
77792057236
34377887914
54575715818
81091323147
130289449044
38859798515
114768107713
86100072195
98284969254
12855923119
119608031566
114788843552
99483748842
28454936947
1039703...

result:

ok 500000 numbers

Test #30:

score: 0
Accepted
time: 736ms
memory: 91824kb

input:

200000 500000
161614 170796 8711
31541 145252 6019
6581 43902 9393
65492 173813 1977
26737 144071 1295
46596 128588 5887
40024 125184 1059
49850 128105 579
145860 156981 8189
23649 39758 2523
92545 186880 5844
99460 181884 2413
40458 176879 1094
101450 111492 4881
15628 29165 7724
70212 94427 7220
3...

output:

15587358611644622
2753354696419528
13032234556657804
11569437841817306
15678266754380351
4774770209393394
7144555280515641
3511975770131904
3216537433659968
14225446872275521
3886046886644282
13600935004052392
614316794520190
8441719504412288
6126977015402654
19225850274049522
13556443075825916
1108...

result:

ok 500000 numbers

Test #31:

score: 0
Accepted
time: 74ms
memory: 35168kb

input:

10 500000
5 7 5364
6 9 195
2 10 2865
1 6 3430
4 7 4892
8 10 96
4 6 2918
1 8 1545
3 5 9282
4 6 92225 34265
4 6 16542 38006
4 8 78850 44308
4 10 12518 8835
1 6 65906 5386
3 6 12511 1337
3 10 2744 76630
2 7 45597 3705
5 8 72929 80974
4 10 95885 74294
5 7 57915 75877
6 10 62811 46853
6 8 64977 88114
8 1...

output:

2073819090
624813212
1769643660
291101794
417920452
255050350
1398114350
549173268
1712179568
2264633334
1732326272
1544717661
1720029066
28366112
1258071772
2415655634
1097710670
863915598
2167180404
2551945589
2255950620
1845962130
1480663976
1109666250
651536563
2393766210
1428725183
1477365478
1...

result:

ok 500000 numbers

Test #32:

score: 0
Accepted
time: 110ms
memory: 35208kb

input:

100 500000
53 58 2341
50 59 8029
29 96 9922
2 42 2537
4 64 8252
45 61 3776
73 87 2728
69 92 8022
5 52 8549
32 38 2100
68 91 5373
31 80 7016
21 62 9706
3 62 1913
5 12 8508
60 79 8014
1 99 3417
17 58 4927
45 59 388
41 92 9324
9 19 5665
71 72 5374
49 98 6745
4 74 3035
45 66 3977
49 76 5262
67 84 6544
3...

output:

113275578588
94811155533
70088383860
67083851893
119017361930
39943371460
162674241147
176183288228
163113256519
118061681904
110402458110
64049779318
107480590890
68976875498
115686471588
136602354006
132493869051
127020415149
55996927769
53377746996
78970027154
67917663935
93618128016
98842580082
...

result:

ok 500000 numbers

Test #33:

score: 0
Accepted
time: 680ms
memory: 91864kb

input:

200000 500000
145185 175065 2436
53356 84599 1290
105557 175136 4540
60977 151141 4942
163917 172758 9403
53860 183870 9961
5112 25159 1855
114711 164151 9716
17733 53577 7274
89123 165488 3664
136 141988 2825
63446 85508 2584
17629 90534 261
81969 158653 41
26512 164537 8184
44294 147894 3009
13794...

output:

10426893441188036
7224297544847883
10657174227740772
8791298429141878
14963476699472786
16464564376772758
8531890388037306
4578989017907610
6346680972886632
5000181689913762
10990458809557436
10119262457473258
4099435763483130
1627314993616369
8861368912679331
8495422887539577
14065742283508675
9404...

result:

ok 500000 numbers

Test #34:

score: -100
Wrong Answer
time: 1273ms
memory: 137148kb

input:

200000 500000
8859 166855 9818
78272 175133 9324
47078 159150 5282
68538 136326 9077
18774 36664 5397
52385 94763 4224
168615 199168 2148
40707 106627 6316
96426 182772 1146
59413 85149 4069
105781 182866 1305
7355 83740 4350
167219 170628 6499
29748 162314 3984
28988 52392 3067
70130 188852 5090
11...

output:

1000923328
2000922314000462171
2000909554000000000
2001846656000000000
730725289641976287
447730651113676684
900095965917182352
1293909919305497253
656823784440904824
898798865792751556
1385145503906622931
591341527537817883
306540705538620312
731545685482956223
1150668143506257090
17964789002923917...

result:

wrong answer 1st numbers differ - expected: '1000462170', found: '1000923328'