QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334196 | #6111. Two Paths | FISHER_ | WA | 1273ms | 137148kb | C++20 | 8.2kb | 2024-02-21 13:57:07 | 2024-02-21 13:57:08 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'