QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334964 | #6111. Two Paths | Terac | AC ✓ | 847ms | 172028kb | C++14 | 9.2kb | 2024-02-22 15:38:39 | 2024-02-22 15:38:39 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO {
#if ONLINE_JUDGE
#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
#else
#define getc() getchar()
#endif
const int IL = 1 << 21, OL = 1 << 21;
int olen = 0;
char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
inline int read() {
register char ch = getc(); register int x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
return x * f;
}
inline double readdb() {
register char ch = getc(); register double x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
if(ch == '.') {
register double b = 0.1;
ch = getc();
while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
}
return x * f;
}
inline int readstr(char *s) {
register char ch = getc(); register int len = 0;
while(!isalpha(ch)) ch = getc();
while(isalpha(ch)) s[++len] = ch, ch = getc();
return len;
}
inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
inline void putc(register char ch) { obuf[olen++] = ch; }
template<class T>
inline void write(register T x) {
if(x < 0) obuf[olen++] = '-', x = -x;
if(x > 9) write(x / 10);
obuf[olen++] = x % 10 + 48;
}
} using namespace IO;
const int N = 2e5 + 10;
const ll inf = 1e15;
int n, q, m, p[N];
ll a[N], b[N];
struct edge {
int to, w, nxt;
} e[N << 1];
vector<int> E[N];
int head[N], ecnt;
void addedge(int u, int v, int w) {
e[++ecnt] = {v, w, head[u]};
head[u] = ecnt;
}
int S, T, fa[N], dfn[N], dep[N], tim;
ll dis[N], mx[N], sec[N], mxid[N], dis2[N];
bool vis[N];
void dfs0(int u, int f) {
if(dis[u] > dis[S]) S = u;
for(int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if(v == f) continue;
E[u].push_back(v);
dis[v] = dis[u] + e[i].w;
dfs0(v, u);
}
}
int top[N];
void dfs(int u, int f) {
dep[u] = dep[f] + 1, fa[u] = f, dfn[u] = ++tim;
for(int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if(v == f) continue;
dfs(v, u);
}
}
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
int L[N], R[N];
namespace st_table {
int st[20][N];
inline int Min(int u, int v) { return dep[u] < dep[v] ? u : v; }
void init() {
for(int i = 1; i <= n; i++)
st[0][dfn[i]] = i;
for(int i = 1; (1 << i) <= n; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = Min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
inline int query(int l, int r) {
int L = 31 ^ __builtin_clz(r - l + 1);
return Min(st[L][l], st[L][r - (1 << L) + 1]);
}
} using namespace st_table;
inline int LCA(int u, int v) {
if(u == v) return u;
if(dfn[u] > dfn[v]) swap(u, v);
return fa[query(dfn[u] + 1, dfn[v])];
}
inline ll Dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[LCA(u, v)]; }
void dfs2(int u, int id) {
top[u] = id;
L[u] = u, R[u] = u;
for(int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if(vis[v] || v == fa[u]) continue;
dfs2(v, id);
int tmp[4] = {L[u], R[u], L[v], R[v]};
for(int i = 0; i < 4; i++)
for(int j = i + 1; j < 4; j++)
if(Dis(tmp[i], tmp[j]) > Dis(L[u], R[u])) L[u] = tmp[i], R[u] = tmp[j];
if(mx[v] + e[i].w > mx[u]) sec[u] = mx[u], mx[u] = mx[v] + e[i].w, mxid[u] = v;
else sec[u] = mx[v] + e[i].w;
}
}
struct ST_table {
ll st[20][N];
void init(ll *a, int n) {
for(int i = 1; i <= n; i++)
st[0][i] = a[i];
for(int i = 1; (1 << i) <= n; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
inline ll query(int l, int r) {
int L = 31 ^ __builtin_clz(r - l + 1);
return max(st[L][l], st[L][r - (1 << L) + 1]);
}
} s1, s2;
inline int get(int u, int v) { return *--upper_bound(E[u].begin(), E[u].end(), v, cmp); }
vector<pair<ll, ll>> t[N << 2];
#define ls x << 1
#define rs x << 1 | 1
inline bool check(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
return (b.second - c.second) * (a.first - c.first) <= (a.second - c.second) * (b.first - c.first);
}
void build(int x, int l, int r) {
t[x].push_back({0ll, 0ll});
if(l == r) return;
ll res = -1e9;
for(int i = l; i <= r; i++) {
// assert(b[i] >= 0);
if(i != l) {
while(t[x].size() > 1 && check(make_pair(res, b[i]), t[x].back(), t[x][t[x].size() - 2])) t[x].pop_back();
t[x].push_back(make_pair(res, b[i]));
}
res = max(res, a[i]);
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
ll query(int x, int l, int r, int L, int R, ll A, ll B) {
if(L <= l && r <= R) {
ll res = -1e14;
if(L < l) res = max(res, A * s1.query(L, l - 1) + B * s2.query(l, r));
if(t[x].size() < 2) return res;
int curl = 1, curr = t[x].size() - 1, mid, ans;
while(curl <= curr) {
// cerr << curl << " "<< curr <<endl;
mid = curl + curr >> 1;
assert(mid >= 1 && mid <= t[x].size() - 1);
// cerr << A << " " << t[x][mid].first <<" " << B <<" " << t[x][mid].second << endl;
if(A * t[x][mid].first + B * t[x][mid].second > A * t[x][mid - 1].first + B * t[x][mid - 1].second)
ans = mid, curl = mid + 1;
else curr = mid - 1;
}
return max(res, A * t[x][ans].first + B * t[x][ans].second);
// return res;
}
ll res = -1e14;
int mid = l + r >> 1;
if(mid >= L) res = max(res, query(ls, l, mid, L, R, A, B));
if(mid < R) res = max(res, query(rs, mid + 1, r, L, R, A, B));
return res;
}
int main() {
// if(system("fc my.out path1.out")) return 0;
// freopen("path1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(), q = read();
for(int i = 1, u, v, w; i < n; i++) {
u = read(), v = read(), w = read();
addedge(u, v, w);
addedge(v, u, w);
}
dfs0(1, 0);
T = S, S = 0;
memset(dis, 0, sizeof(dis));
dfs0(T, 0);
swap(S, T);
dfs(S, 0);
init();
int t = T;
while(t) { p[++m] = t; vis[t] = 1; t = fa[t]; }
reverse(p + 1, p + 1 + m);
for(int i = 1; i <= m; i++)
dfs2(p[i], i);
for(int i = 1; i <= m; i++)
a[i] = dis[p[i]] + mx[p[i]];
s1.init(a, m);
for(int i = m - 1; i; i--)
dis2[p[i]] = dis2[p[i + 1]] + dis[p[i + 1]] - dis[p[i]];
for(int i = 1; i <= m; i++)
b[i] = dis2[p[i]] + mx[p[i]];
s2.init(b, m);
build(1, 1, m);
// return 0;
while(q--) {
ll ans = 0;
int u = read(), v = read();
ll A = read(), B = read();
if(top[u] == top[v]) {
int f = LCA(u, v);
if(u == f) {
ll a = max(Dis(u, S), Dis(u, T));
int t = get(u, v);
ll b = max(Dis(v, L[t]), Dis(v, R[t]));
ans = max(ans, a * A + b * B);
}
else if(v == f) {
ll a = max(Dis(v, S), Dis(v, T));
int t = get(v, u);
ll b = max(Dis(u, L[t]), Dis(u, R[t]));
ans = max(ans, b * A + a * B);
}
else {
int lca = LCA(u, v);
ll a1 = max(Dis(u, S), Dis(u, T));
ll a2 = max(Dis(v, S), Dis(v, T));
ll b1 = 0, b2 = 0;
int t1 = get(lca, u), t2 = get(lca, v);
b1 = max(Dis(u, L[t1]), Dis(u, R[t1]));
b2 = max(Dis(v, L[t2]), Dis(v, R[t2]));
ans = max({ans, a1 * A + b2 * B, b1 * A + a2 * B});
}
}
else {
int f1 = top[u], f2 = top[v];
if(f1 > f2) swap(f1, f2), swap(u, v), swap(A, B);
int fa1 = p[f1], fa2 = p[f2];
int t1, t2;
if(fa1 != u) t1 = get(fa1, u);
else t1 = u;
if(fa2 != v) t2 = get(fa2, v);
else t2 = v;
ll b1 = max(Dis(u, L[t1]), Dis(u, R[t1]));
ll b2 = max(Dis(v, L[t2]), Dis(v, R[t2]));
ans = A * b1 + B * b2;
if(u != fa1) ans = max(ans, A * b1 + B * max(Dis(v, S), Dis(v, T)));
if(v != fa2) ans = max(ans, A * max(Dis(u, S), Dis(u, T)) + B * b2);
ll c1 = dis[u] - dis[fa1], c2 = dis[v] - dis[fa2];
if(mxid[fa1] == t1) c1 += sec[fa1];
else c1 += mx[fa1];
if(mxid[fa2] == t2) c2 += sec[fa2];
else c2 += mx[fa2];
c1 = max(c1, Dis(u, S)), c2 = max(c2, Dis(v, T));
ans = max(ans, A * c1 + B * c2);
if(f1 + 1 <= f2 - 1) ans = max(ans, A * c1 + B * (s2.query(f1 + 1, f2 - 1) - dis2[fa2] + dis[v] - dis[fa2]));
if(f1 + 1 <= f2 - 1) ans = max(ans, A * (s1.query(f1 + 1, f2 - 1) - dis[fa1] + dis[u] - dis[fa1]) + B * c2);
// ll X = -1e9;
if(f1 + 1 <= f2 - 1) ans = max(ans, query(1, 1, m, f1 + 1, f2 - 1, A, B) + A * dis[u] - 2 * A * dis[fa1] + B * dis[v] - B * dis2[fa2] - B * dis[fa2]);
// for(int i = f1 + 1; i <= f2 - 1; i++) {
// if(i != f1 + 1) ans = max(ans, A * (X - dis[fa1] + dis[u] - dis[fa1]) + B * (dis2[p[i]] + mx[p[i]] - dis2[fa2] + dis[v] - dis[fa2]));
// X = max(X, dis[p[i]] + mx[p[i]]);
// }
}
printf("%lld\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 60136kb
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: 7ms
memory: 51260kb
input:
2 1 1 2 1 1 2 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 55316kb
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: 63ms
memory: 65484kb
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: 108ms
memory: 72892kb
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: 326ms
memory: 109684kb
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: 63ms
memory: 65548kb
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: 95ms
memory: 72812kb
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: 343ms
memory: 107656kb
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: 64ms
memory: 60964kb
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: 105ms
memory: 69692kb
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: 368ms
memory: 109820kb
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: 68ms
memory: 60540kb
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: 114ms
memory: 73740kb
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: 369ms
memory: 109872kb
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: 65ms
memory: 64748kb
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: 73152kb
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: 332ms
memory: 109764kb
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: 62ms
memory: 59000kb
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: 115ms
memory: 71048kb
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: 371ms
memory: 109840kb
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: 64ms
memory: 62460kb
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: 110ms
memory: 76932kb
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: 352ms
memory: 107856kb
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: 71ms
memory: 58996kb
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: 109ms
memory: 74516kb
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: 350ms
memory: 107776kb
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: 69ms
memory: 62568kb
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: 96ms
memory: 69572kb
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: 331ms
memory: 109820kb
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: 71ms
memory: 66096kb
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: 73676kb
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: 346ms
memory: 109736kb
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: 0
Accepted
time: 796ms
memory: 171324kb
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:
1000462170 2000922314000000000 2000909554000000000 2000924340000000000 730725289641976287 447730651113676684 900095965917182352 1293909919305497253 656823784440904824 898798865792751556 1385145503906622931 591341527537817883 306540705538620312 731545685482956223 1150668143506257090 17964789002923917...
result:
ok 500000 numbers
Test #35:
score: 0
Accepted
time: 824ms
memory: 170552kb
input:
200000 500000 57015 149285 9879 28544 152998 3713 25802 110059 4795 86853 107388 8494 176076 191815 2808 165752 169376 8008 24017 30541 1844 129796 188853 5103 1621 124316 7435 12073 24070 7934 103916 136440 6319 112433 120519 5416 8111 99401 3395 125150 162346 1698 78140 144632 5049 48323 81048 576...
output:
1002626517 2005233370000000000 2005245938000000000 2005253034000000000 739346057543654683 920744266636160962 452498520092735287 1530300605349377829 1116099106255822467 683735009718297838 711589829297811835 1577214235179306567 1658979091839100176 1412184796341697246 533924772459843599 236895297048860...
result:
ok 500000 numbers
Test #36:
score: 0
Accepted
time: 837ms
memory: 172028kb
input:
200000 500000 115815 123648 6156 79253 111480 6977 84185 128329 1475 79473 163105 9760 61239 186905 1357 149721 191564 891 64587 78969 3684 14597 182366 1231 10025 90751 5090 20216 36500 2874 131576 169512 4488 50373 80542 5730 11827 91891 2494 174330 184277 2104 1652 94882 3339 28264 32408 525 6928...
output:
999975234 1999932062000000000 1999948824000000000 1999950468000000000 661591716089270848 915680199624585766 1434167854370962636 1779749366161518808 287115300068686987 905487213139243304 1212623617364534034 551794304484333294 1277825556854361570 988320702201908892 658021069472979274 35707211466928469...
result:
ok 500000 numbers
Test #37:
score: 0
Accepted
time: 828ms
memory: 168812kb
input:
200000 500000 131562 178676 2632 46354 150847 1815 92095 93512 1758 62830 146374 3230 89760 174186 7084 2532 18290 5205 6197 113403 5352 99747 165295 1910 90134 150784 2035 29848 186120 535 61174 85283 9598 128455 177567 9391 114655 122068 1372 184161 199568 8699 141462 189507 2329 76272 118780 4386...
output:
1000726846 2001448888000000000 2001435860000000000 2001453692000000000 904479579881274072 954395157655097898 815516157008918489 1024173332541872537 1369663762863014380 408134896988859408 374588771267388033 899578310674017693 996295518644283749 584709334940985982 1642736140830176786 11746452443321951...
result:
ok 500000 numbers
Test #38:
score: 0
Accepted
time: 818ms
memory: 170708kb
input:
200000 500000 14959 117058 9733 11185 151871 8292 30899 166428 8575 20184 138441 4931 147251 159450 7236 94070 171081 6943 146591 191476 5050 39370 190243 2644 170789 176248 9176 40408 45918 2048 121599 178547 8136 83319 152223 1589 53811 80803 4138 40375 127717 7296 102970 195093 1628 120443 173722...
output:
1001262207 2002523934000000000 2002519634000000000 2002524414000000000 1337893225166326277 996791973320113816 617565038561160030 464515405428083409 778505173092407457 1471927642382407140 1508479931599231610 554439415324587232 1222403590045493116 264963640459200637 85932016709412804 16299507434853534...
result:
ok 500000 numbers
Test #39:
score: 0
Accepted
time: 687ms
memory: 168888kb
input:
200000 500000 58135 125858 1 114725 126732 1 23205 57286 1 14057 21691 1 22648 66157 1 142596 192969 1 38724 118161 1 56649 150881 1 93568 144640 1 109964 122400 1 2426 3133 1 46327 109711 1 24759 125146 1 12369 54466 1 181501 194617 1 12182 106913 1 53200 72899 1 108457 177795 1 157064 157836 1 294...
output:
199998 399996000000000 399996000000000 399996000000000 65058057698608 251631442905875 148179521041673 50828396157631 55032060850336 95065279717206 295797388272588 157214174484965 294474833602594 234063224777035 221269976164186 284117217588189 126028337534274 94561379255032 272114672536140 3602520274...
result:
ok 500000 numbers
Test #40:
score: 0
Accepted
time: 669ms
memory: 167764kb
input:
200000 500000 54737 121996 10000 116805 159884 10000 14824 108446 10000 125782 138095 10000 134214 198690 10000 49064 100641 10000 14918 94337 10000 41946 198028 10000 59686 186633 10000 23800 53431 10000 61859 196561 10000 63408 106000 10000 44826 162357 10000 139872 174148 10000 73340 129012 10000...
output:
1999980000 3999960000000000000 3999960000000000000 3999960000000000000 2112939366422610000 1652588792680600000 3534944192185520000 2138523765864690000 1920653337754830000 2371081801553730000 1674852843724050000 3689778263812170000 1761900838750970000 2628927029796920000 1071933251689020000 180237521...
result:
ok 500000 numbers
Test #41:
score: 0
Accepted
time: 705ms
memory: 167768kb
input:
200000 500000 18280 146267 1 53153 53814 1 40752 86560 1 152092 173596 1 36755 144659 1 23045 62588 1 111028 194440 1 91938 122143 1 141402 170123 1 38669 154348 1 128719 173132 1 10873 101529 1 1501 188904 1 71638 181803 1 2944 197056 1 142913 174843 1 25120 70013 1 34836 41517 1 59326 147528 1 732...
output:
199998 399996000000000 399996000000000 399996000000000 342854506131046 269405581975706 58744792707530 299222967022625 150965427026454 269817943665195 143406572495313 177366207171208 99649175313741 248797580465156 238923214616007 147684064592059 221983786700072 102177339750258 150928744519870 1088691...
result:
ok 500000 numbers
Test #42:
score: 0
Accepted
time: 712ms
memory: 167552kb
input:
200000 500000 87775 116743 10000 120737 141840 10000 58322 148456 10000 12756 142058 10000 108617 117902 10000 7265 173904 10000 63833 68382 10000 77267 160237 10000 38900 68259 10000 33888 166138 10000 14435 145218 10000 5592 82242 10000 103098 112490 10000 42053 103885 10000 67942 180352 10000 114...
output:
1999980000 3999960000000000000 3999960000000000000 3999960000000000000 2832053943134980000 578101600135680000 1625586053880290000 2201418046890190000 2513634609619770000 275856912403430000 2339656623176070000 3856070775043110000 3234974266323690000 642938928362350000 1661703339491790000 316828535182...
result:
ok 500000 numbers
Test #43:
score: 0
Accepted
time: 801ms
memory: 160688kb
input:
199999 500000 177639 187054 10000 53633 58838 10000 156394 174041 10000 63775 97370 2104 73163 193678 5823 53573 141187 8296 61961 75498 7709 103044 107827 7712 1426 120114 6650 56610 191872 10000 135673 140552 10000 57968 137914 10000 72661 94425 10000 7833 93730 10000 39678 94555 10000 59304 68766...
output:
6154260174064 9802363109918 1886160921750 10385842550840 9141495445947 17276485166694 8979852635025 1503083743564 859109166973 1848113477653 12176991099885 13328353929048 2277048140304 906773562549 2607468499258 1592776164772 11074948869980 2192234739187 1789772831430 12541878653411 11758993185796 9...
result:
ok 500000 numbers
Test #44:
score: 0
Accepted
time: 819ms
memory: 160628kb
input:
199999 500000 6035 197909 10000 31501 51143 8859 57845 88388 1421 45009 78895 10000 16152 172707 10000 69263 178748 1894 79822 164403 3843 8684 16020 993 5088 144742 9726 97598 154393 10000 59598 101962 10000 137754 150035 9603 126803 133637 9961 125803 133265 2766 84357 176033 10000 72627 89689 504...
output:
139947406389 5891473599866 14129740182318 134563048125 5337509412672 11927036858913 14665421541730 10689272275724 7118330595063 5799028598007 9368118773750 14514056337724 6517790592887 14785213111254 3330280902198 4012804398587 8519243407321 10972807360957 8016634890364 8044438238929 3533646052128 1...
result:
ok 500000 numbers
Test #45:
score: 0
Accepted
time: 687ms
memory: 154932kb
input:
199999 500000 37086 96937 3878 8854 123271 10000 97720 151315 10000 117078 174984 10000 41065 156400 10000 41008 54529 10000 5637 58551 1608 24943 105226 10000 85352 124448 10000 80107 190498 4195 40647 110809 10000 9853 120720 10000 53452 116676 10000 7414 124839 1448 38914 97935 10000 118746 15317...
output:
880489084944 1564955634622 4625556426455 1837465431805 6715848417678 5147613692434 392484178917 5441314046262 3218755015930 4105699034233 4852148150847 9753180893784 9511753693828 6096146372693 7418534841240 8808393073543 1436654136899 4419285430176 7740953215478 2197521607860 2597450179116 24944584...
result:
ok 500000 numbers
Test #46:
score: 0
Accepted
time: 785ms
memory: 159552kb
input:
199997 500000 58336 78659 10000 155915 162205 10000 18740 81958 10000 183617 195225 10000 42900 104488 10000 92366 124938 1068 58152 74131 1924 75947 127093 3040 47409 76491 10000 140741 196054 8696 32892 168884 10000 20255 197006 10000 121339 180373 9460 73239 105444 10000 51257 159528 10000 107853...
output:
18983503917876 6191307941016 29485438589132 7748110302160 3493742050476 28548777468324 20022881315580 9130183760728 98735154236 10212893972452 5622767047000 16902277986112 5615816223872 9280090611488 10105451736288 16390204096344 6527242330732 5040452687020 30106777184320 7386959092584 1906486323076...
result:
ok 500000 numbers
Test #47:
score: 0
Accepted
time: 658ms
memory: 153496kb
input:
199997 500000 95130 126673 10000 23194 113538 10000 20400 177565 10000 17309 197072 3754 104197 199869 10000 42847 73581 10000 60747 192806 10000 70211 97307 1838 10434 39403 10000 72581 97798 10000 48535 60551 10000 162580 191244 10000 193160 193666 5010 95399 117565 10000 57551 127181 4964 66080 1...
output:
18000635747955 40873165756962 38836000955909 4109576635643 7740534771903 12292681255583 30742508887536 26783417703210 17785170421344 17143079971779 8397978001407 1609713803698 1593075569163 20358263008434 16049544196671 42576091411573 20019742470630 11026945717341 3971844510660 21537404514680 477331...
result:
ok 500000 numbers
Test #48:
score: 0
Accepted
time: 636ms
memory: 143292kb
input:
199999 500000 9377 100040 5658 43987 53942 10000 44653 95734 10000 40082 43909 3846 75294 94733 9871 136720 151476 10000 35431 160481 10000 21663 157861 10000 69456 175492 6421 132213 137870 10000 98664 173600 8510 99175 167461 10000 40269 75816 10000 57882 145247 10000 86708 163753 10000 89488 1909...
output:
1923307476548 4629429353282 449636274258 2042923036477 248740344047 3097165863343 4458251893963 5148839103400 358259464634 6528493015867 5155429852738 587813729689 6261659040121 2684182818305 3688100894521 3619144346496 3624700575816 1791484288371 1677481696899 1893696697639 1467412936168 6077048581...
result:
ok 500000 numbers
Test #49:
score: 0
Accepted
time: 722ms
memory: 153396kb
input:
199999 500000 61356 195745 10000 37207 64305 10000 104123 185276 10000 11544 38521 5396 31494 69204 10000 70439 121675 10000 73162 128463 10000 36926 61221 10000 53084 141043 6835 96744 151690 1356 48996 154807 8721 31010 193117 10000 15782 47886 10000 36812 153556 7224 86399 146538 10000 154636 172...
output:
12274022386229 12079249691431 16827965643855 2823531420113 18511485486974 20323485132402 3490682672358 11799881034641 2785231722259 360586142523 5277509347609 9054173014819 6167495103936 10545831703538 10570710371223 8418604622239 1774963709809 17519192338756 9439860745380 13954542976863 19499477859...
result:
ok 500000 numbers
Test #50:
score: 0
Accepted
time: 640ms
memory: 141812kb
input:
199995 500000 12878 43249 10000 30272 197071 10000 20740 178838 10000 21518 48105 9733 144837 157876 10000 55550 147981 10000 14819 146293 10000 44396 133267 10000 63687 185314 3312 78127 126130 10000 157449 157777 696 164379 168306 1334 76866 198964 10000 3530 133177 1656 35576 96915 10000 60206 66...
output:
593746504160 82991834992 1931351112739 4783928456366 2786409296799 1757476810145 83701165348 3901539338372 2381351047770 2713183269835 2843742359216 1795329679240 3991174790394 1822034549534 1574125021711 4129639547957 3830352036248 1218716189524 68446457129 4216730991896 1575981894826 914269813066 ...
result:
ok 500000 numbers
Test #51:
score: 0
Accepted
time: 698ms
memory: 148824kb
input:
200000 500000 46676 113849 6740 101206 126909 10000 19529 80553 8940 68426 146456 10000 18205 35579 10000 39475 187507 3090 124166 147338 10000 68921 161366 2360 128983 174966 10000 45835 53618 10000 113138 183819 10000 65360 197473 10000 22612 152918 10000 91325 109086 6048 17794 38027 1304 34812 8...
output:
9944891454424 15949051268688 3617483933544 2282613690420 619452010068 12428314409592 13936664159460 10962944594956 12467078293196 6780449470940 3315805023160 16900122707688 10512303629184 9153271869972 7925999354940 10479965266560 4800408506964 7143314327008 9187351798256 11299529851596 563439058645...
result:
ok 500000 numbers
Test #52:
score: 0
Accepted
time: 716ms
memory: 153084kb
input:
199999 500000 155223 168937 10000 118162 178165 10000 80438 191072 5062 23772 147846 7213 87055 99749 9065 72798 174774 4632 29522 133851 10000 49223 97059 10000 176384 195077 10000 153416 185126 10000 72786 76808 9119 3031 141247 10000 72093 83183 10000 43082 69281 10000 12637 61286 10000 79522 126...
output:
1453826037145 1383674338329 12746221563571 15322265205661 29340338682109 1506774828050 1780797959671 31101495294067 1454124702148 25279385970354 13350358395878 27150159297607 18564627534280 23488115321805 19723673513446 3836076823917 9806200137934 12468193355418 15143567278618 17404082189908 2519328...
result:
ok 500000 numbers
Test #53:
score: 0
Accepted
time: 847ms
memory: 141024kb
input:
200000 500000 189505 195026 5261 102020 186607 10000 53680 110202 10000 62732 102799 4768 52784 132897 4172 52784 147876 4252 84933 150689 2827 52784 178069 6961 15704 94742 9584 121463 125974 10000 25914 79909 6687 52784 177265 8836 64161 138281 8181 9690 94405 5589 143629 189505 2419 52784 143950 ...
output:
5051019581659 908949291118 183477881123 3081953986095 4564048522496 2157783044887 4695100210301 2456194528051 4271433982439 2085348990633 4670659220354 4878236042866 756269217332 245770016036 4712320387035 56389223519 498045939678 1464734062316 4323611232809 5131117472566 5107659335238 587222729445 ...
result:
ok 500000 numbers
Test #54:
score: 0
Accepted
time: 803ms
memory: 141056kb
input:
200000 500000 133872 139325 3596 29904 48660 5952 142727 146550 3997 101923 103275 10000 29904 65269 5639 75294 161927 6407 93737 137890 10000 19551 139325 3747 98693 139325 4277 50523 139325 7371 139325 163701 6182 28281 29904 2855 83198 132703 10000 136565 174419 1775 139325 164389 4150 29904 1389...
output:
939148732265 2680048941941 4420402804290 4846662110815 274142543739 2176562314122 1852829117888 1878277366172 2387933426578 1538584743245 4697862507970 3645664203340 2066956170559 1936945764254 440637053613 2732551051938 481589548122 2755853785947 2757256281895 2879588077359 1405299494284 1237171686...
result:
ok 500000 numbers
Test #55:
score: 0
Accepted
time: 803ms
memory: 139100kb
input:
200000 500000 43387 154874 3422 65640 93811 5022 93811 154048 8592 43387 183783 2219 93811 130903 4365 26287 93811 4816 93811 119205 8694 44796 89552 9138 85974 90127 2376 23641 93811 9701 93811 189035 5514 16270 43387 9405 167089 169098 6246 43387 71973 8020 43387 176218 131 56832 197102 10000 9982...
output:
786064597703 4986983439657 4109613343675 1435665772265 349316658358 924421160874 4312537368758 3160481898147 2860266913963 3763704907695 4966950706033 589951634610 5277006120548 2183079055509 4151866015185 3507468409634 4886392641421 2810282922977 1523707654762 1754976014459 93983928396 876028983136...
result:
ok 500000 numbers
Test #56:
score: 0
Accepted
time: 717ms
memory: 137292kb
input:
200000 500000 67936 71453 6067 31640 44028 4813 135929 171669 10000 123902 147440 4726 147440 186229 3604 11059 31640 9840 180150 184339 10000 31640 101877 2462 2198 31640 1822 116358 190869 9434 105076 106716 10000 55687 141117 1288 38355 137359 10000 147440 183134 8627 16502 147440 8837 147440 174...
output:
747893835297 873114660110 1860455089930 418472745006 2491480242268 1175537418690 1695006046660 803981627580 1211513175406 455845721423 1454831147203 3198269914820 1338055547825 3281115569601 3364100974984 213809197100 2458537932114 89888415570 639437510094 2331646442161 62118075340 2111630245477 241...
result:
ok 500000 numbers
Test #57:
score: 0
Accepted
time: 785ms
memory: 140000kb
input:
200000 500000 44570 57642 10000 32817 152059 7949 81799 91476 9660 91476 191584 5664 15976 92566 10000 32817 191789 7973 41644 91476 8691 56453 91476 4998 45028 86089 4914 3979 56945 2514 39830 68149 10000 77728 107638 10000 32817 151688 6336 78961 135706 5120 49878 69100 10000 74739 134700 7172 914...
output:
3548059022172 6030626139092 8568965843732 8887820160380 3566737295988 5586198541348 5583732560264 8522076300802 4703332706984 3445753738472 8607976190514 4120375167232 7684776862434 7048069429924 5442122197840 5455461764880 8426917686132 6279208346908 951404105796 5318691502134 953266487828 62045694...
result:
ok 500000 numbers
Test #58:
score: 0
Accepted
time: 659ms
memory: 136916kb
input:
200000 500000 9253 76614 10000 106773 142647 10000 8978 38819 5520 81329 109796 8812 84201 139836 10000 142701 159787 10000 42231 199856 10000 82062 189589 7104 70924 99991 10000 33518 133908 6813 33518 194499 4250 8978 188421 6599 33518 160278 4881 33518 142393 482 33518 135293 7819 83232 126802 10...
output:
9768810446864 9962627320672 2456140051183 8292679198678 664143235679 13637542221996 12485898727188 8349771431262 6747382607710 15954671628180 15893105958568 7917108069689 3467627617261 2207919431760 5956102633798 13717268823495 14746401598176 10319574274691 10561227876010 12388820515135 986695154850...
result:
ok 500000 numbers
Test #59:
score: 0
Accepted
time: 702ms
memory: 135404kb
input:
200000 500000 182388 199500 10000 63081 191483 10000 29226 76792 10000 13717 167193 9483 70270 172602 10000 6276 13717 4594 28965 109050 1344 119217 164626 6114 13717 198125 8252 107613 148449 10000 13717 172538 237 37676 54022 6481 50284 117096 4352 23043 123924 5706 54022 197235 1930 47420 195642 ...
output:
1847381225419 1264842360115 834224481232 2226697032138 2332552009280 1403526992478 868388956661 557094342734 67236368562 190852373454 807734684597 2120061064228 2198999258492 292296224910 1166372324066 581466867437 1998526492515 1868794058326 1456472868383 626808054797 2305465416726 11814652589 6293...
result:
ok 500000 numbers
Test #60:
score: 0
Accepted
time: 734ms
memory: 136020kb
input:
200000 500000 5691 34034 10000 132381 197524 10000 148409 181471 6018 59782 183412 9778 24502 108517 10000 81726 155124 9990 18162 148409 7145 23970 148409 2251 49865 181610 3860 148409 185273 4070 35703 148409 3502 49865 196662 3404 148409 184412 8790 51865 194469 10000 49865 157909 3146 49865 1671...
output:
1132120479367 1792129233802 1277637108246 6525526526162 4895590429693 5397018206364 5151504234445 1796246024114 4170426416229 2194506397316 5389171523192 2858866952498 1944312203086 4572210114145 4428253424967 4324471885157 5421858624141 6447149501744 5742140892245 5880411034415 6808218386419 659891...
result:
ok 500000 numbers
Test #61:
score: 0
Accepted
time: 674ms
memory: 130032kb
input:
200000 500000 120752 195946 1313 15233 195946 9397 4633 79724 3744 62274 127681 10000 3487 71392 2996 108670 193270 10000 13491 58499 10000 3254 75019 1504 3254 157444 1422 3254 45367 5800 3254 192144 3365 78085 195946 8765 14885 195946 7242 6533 124374 8324 87848 178054 1199 61847 177846 10000 1090...
output:
746796865016 691040829251 994155264768 1729766005545 912782528535 1076703641416 193011406551 299253313673 520569166820 1362016771281 1052466673298 570691024850 676538501463 737831006514 1499713171930 1718869679352 1357772822392 1739094047986 72511911595 1790681356364 1281436308519 521686891456 61057...
result:
ok 500000 numbers
Test #62:
score: 0
Accepted
time: 752ms
memory: 137008kb
input:
200000 500000 15287 68501 10000 7075 172606 5380 534 2898 3116 97818 168218 750 36251 143414 10000 534 94155 2553 534 82550 538 154936 168218 3796 51356 110480 10000 162635 180725 10000 74682 98059 10000 54968 182694 4150 103074 168218 9460 99035 168218 226 114360 168218 1151 103040 103563 3624 1295...
output:
2295167140352 1806569915892 3555319080190 847573656096 2247193623502 657880069078 3028599412644 4219700644246 2817620839724 4872694694984 3766841436740 288161586422 3035390124228 736880341426 4401421431264 80524519862 456305846968 4795583113986 811001201632 1741688812084 3624072066696 5519662462186 ...
result:
ok 500000 numbers
Test #63:
score: 0
Accepted
time: 710ms
memory: 135328kb
input:
200000 500000 40883 167547 4224 46018 90251 10000 112479 189078 10000 67705 86647 7674 86647 144486 7642 114893 120878 10000 40883 58874 2194 20695 40965 1400 52544 86647 5740 35700 102805 6832 7858 86647 5324 9418 171083 10000 18064 166593 10000 21439 41606 10000 40883 92280 3550 84110 166514 10000...
output:
6108011148519 9502918170252 6721065349061 6497419327042 9760028616926 2961183808921 3642326902880 6292848964558 2255299336701 6468504888538 3752592287186 10414094502065 2218770098187 605602518641 6036791932052 10535361462701 7354246522159 9812111254888 4473865134591 6023895639540 7566028630282 51520...
result:
ok 500000 numbers
Test #64:
score: 0
Accepted
time: 295ms
memory: 76228kb
input:
200000 500000 73429 170969 4821 7545 73429 8574 19132 73429 578 73429 98049 628 15167 73429 4167 73429 178762 9210 73429 194425 277 73429 138260 8355 73429 101342 4105 73429 148078 3848 27870 73429 3665 73429 171295 444 73429 103562 2622 14664 73429 7250 73429 171516 9082 73429 169316 2379 73429 986...
output:
150746475 156345936 170646480 95029488 54869598 140872896 132059802 110519994 39065184 150770700 70522506 101252500 68692708 112654011 90661350 123056700 110668129 53520652 62314980 158260126 184049110 96595707 96410525 144711038 110043010 116074078 99622916 170267250 50754571 109560987 138947154 14...
result:
ok 500000 numbers
Test #65:
score: 0
Accepted
time: 312ms
memory: 73272kb
input:
200000 500000 56681 174064 574 133322 174064 6319 16923 174064 704 59974 174064 5700 60921 174064 440 3167 174064 1560 44477 174064 5613 7421 174064 5241 7764 174064 3988 76949 174064 1633 128239 174064 9326 27166 174064 8218 137315 174064 5472 105439 174064 6355 28814 174064 7523 107669 174064 4116...
output:
96275298 67372772 94915925 62469265 108522828 106509143 122088956 99607794 88209745 123574110 71151528 120223740 52723011 46030765 47121620 125960037 86013252 63422646 63086240 143151465 81200000 121522477 76180536 170042400 85281336 112964958 51397980 81378570 98824475 106094030 68137914 180699435 ...
result:
ok 500000 numbers
Test #66:
score: 0
Accepted
time: 280ms
memory: 76168kb
input:
200000 500000 136018 176757 889 101799 176757 2941 3298 176757 3723 89681 176757 1731 120663 176757 5607 25701 176757 8060 72743 176757 8707 101340 176757 923 176757 199200 9325 87816 176757 8942 157709 176757 5744 153462 176757 3779 157907 176757 3416 152468 176757 5322 176757 181575 6968 167697 17...
output:
141756450 100421493 69219048 101662113 168816018 45102008 124533216 24640668 81405165 172964862 181218940 45252892 61702904 144071340 94727160 92649252 89851950 80335872 171994020 141939462 47638934 155596532 105638370 72613320 41763876 140876253 99105220 65620800 83966872 78871380 131312094 6318540...
result:
ok 500000 numbers
Test #67:
score: 0
Accepted
time: 194ms
memory: 89564kb
input:
200000 500000 170969 182851 4821 7545 45628 8574 19132 37369 578 98049 178987 628 15167 70970 4167 171446 178762 9210 64877 194425 277 107273 138260 8355 69392 101342 4105 146278 148078 3848 27870 48002 3665 165399 171295 444 103562 128121 2622 14664 139225 7250 63548 171516 9082 40915 169316 2379 9...
output:
96520757113 68950916352 52372297037 99607184960 114043071087 83003001127 68493985746 123451862191 69936594032 125263946125 55948375724 32893941354 46988591451 47746774749 31579539334 55072518240 43924352709 98225327537 45396042090 6154103451 54180387387 92163290736 47143691968 18441572786 6916227922...
result:
ok 500000 numbers
Test #68:
score: 0
Accepted
time: 198ms
memory: 91672kb
input:
200000 500000 42226 56681 574 40311 133322 6319 16923 35337 704 59974 71071 5700 8346 60921 440 3167 141903 1560 44477 51424 5613 7421 107081 5241 7764 93501 3988 14211 76949 1633 74172 128239 9326 27166 65805 8218 82728 137315 5472 105439 193490 6355 28814 67043 7523 107669 164560 4116 91468 139442...
output:
57480012300 54062661733 55666531568 62832803934 83644293972 98644747846 30739318889 100523059149 133890725797 113985154757 123869023998 89650671147 71843371656 44549480290 124221609162 59377536101 19561257784 117432897019 86713958292 63159473731 129045253550 46622027490 26887410321 97071340407 12531...
result:
ok 500000 numbers
Test #69:
score: 0
Accepted
time: 179ms
memory: 91680kb
input:
200000 500000 3898 136018 889 101799 184657 2941 3298 77311 3723 38082 89681 1731 36003 120663 5607 25701 64751 8060 69470 72743 8707 101340 193195 923 42288 199200 9325 49175 87816 8942 33964 157709 5744 153462 199569 3779 102828 157907 3416 37704 152468 5322 44608 181575 6968 73861 167697 5611 229...
output:
111258489343 115735237926 70536038445 86078282470 71490950430 71701712600 62066560779 44908623364 116125170205 63675003059 132166682907 41715103340 85515152628 96006858669 105916985333 69023525476 102975973459 109512860907 124734990461 69521311759 73031223018 42562362359 104267684272 122953330600 54...
result:
ok 500000 numbers
Test #70:
score: 0
Accepted
time: 191ms
memory: 89632kb
input:
200000 500000 147434 162944 4821 113271 154872 8574 63837 70988 578 47627 82859 628 64917 87647 4167 58277 151709 9210 21265 60956 277 82178 182277 8355 37110 71343 4105 43543 96028 3848 56566 68268 3665 118191 142291 444 15348 171644 2622 5183 121311 7250 83179 157871 9082 18923 49677 2379 68295 11...
output:
93271465652 70128842816 57330666576 110412740518 111782034111 86653411411 62884991266 119933132370 72775786618 112922076511 62058101236 34466747362 48954100282 48533516322 30924147268 57166372080 41975296756 96120550358 49316537025 7099704770 50967342813 91474967355 47031950297 19368814088 668482510...
result:
ok 500000 numbers
Test #71:
score: 0
Accepted
time: 181ms
memory: 93728kb
input:
200000 500000 17241 22395 574 62134 96773 6319 44389 102997 704 11285 194146 5700 179837 197562 440 7405 175969 1560 52064 55276 5613 147504 184990 5241 15151 94017 3988 126048 151852 1633 122155 141346 9326 18529 107129 8218 66561 77845 5472 27253 137607 6355 82265 101518 7523 3079 151558 4116 1316...
output:
54094298336 62960610697 55891705900 65927309485 90206831628 94552389811 30735381789 100823530108 135201441225 126449968802 121913998986 86936404712 64502359583 46562117000 119114404868 61390814569 18302391568 111238777198 86093106279 61139409990 115461073530 47876543229 26643607200 95918719107 11462...
result:
ok 500000 numbers
Test #72:
score: 0
Accepted
time: 203ms
memory: 91668kb
input:
200000 500000 128269 150094 889 74092 137159 2941 15984 121961 3723 48370 121604 1731 7727 97285 5607 16574 75978 8060 70783 198649 8707 34883 37898 923 11046 142855 9325 48714 127630 8942 118439 144545 5744 58830 195044 3779 134888 174356 3416 107178 178954 5322 80456 166946 6968 40637 146134 5611 ...
output:
112298530134 117625138281 79051804146 90689451716 79177422876 80279680565 70416171144 47230389712 128582056801 69241472569 132083367850 40452042332 85116368304 99160684418 105944322164 79445333700 107000272339 105352879563 115953370542 74866938621 66134361878 42243220488 111946985256 133553952324 60...
result:
ok 500000 numbers
Test #73:
score: 0
Accepted
time: 40ms
memory: 103028kb
input:
100000 10 11144 99817 9379 46222 80615 4748 48124 80167 9522 24254 39453 7959 27125 44714 1303 47339 63723 6194 27606 37044 2334 3247 27044 8602 17154 46539 1405 11466 36233 6738 9221 90634 6381 27828 70637 7127 56232 56358 6441 45235 71901 7651 10673 28017 3797 7093 80868 5206 15814 97465 8609 6554...
output:
3029676008066994 2308586298538575 848703709157613 2502830434971719 3873934927729468 4298115894022313 2739180653224424 3704496181494105 3676518979478792 4599240524788351
result:
ok 10 numbers
Test #74:
score: 0
Accepted
time: 787ms
memory: 139068kb
input:
200000 500000 92080 195520 8523 32057 190571 124 131851 183457 1648 166355 180972 5732 45870 133085 1909 66227 92069 1689 37418 155321 2968 68089 73599 10000 32057 164036 7084 36963 142993 10000 32057 57847 7749 97684 195375 8001 119875 184087 10000 32057 114886 3870 135068 145200 10000 140779 16662...
output:
4643813748762 659124066090 2791960658242 4449028983407 4694959521344 2339951105126 4908578461776 1732193849948 2375297367714 3599326344612 4555246556927 2609942367744 4659467801025 379197447085 3601811443473 3772596855100 3455044725502 3459844448658 2560098098443 2226823433482 2204250526513 45009045...
result:
ok 500000 numbers
Test #75:
score: 0
Accepted
time: 750ms
memory: 138984kb
input:
200000 500000 11332 155323 4642 17192 98867 7871 86494 180211 2172 115221 122791 10000 21006 89059 2850 63047 83175 10000 63269 145451 9739 44407 63269 1787 45599 108184 808 74901 100674 10000 19506 125338 10000 11292 45438 10000 62950 63269 4880 98867 123028 6206 71375 98867 6786 61009 191595 3728 ...
output:
860859257723 1996869088746 3404780909991 695148218388 5122168949032 3709757645145 1988616540519 256247240106 2530157537503 4443914604645 4861567262407 1835601601352 3749802024226 609214470643 5336730177563 1143775584513 2298568157350 1897537192534 4620880445100 1222435517411 179091786101 35449635280...
result:
ok 500000 numbers
Test #76:
score: 0
Accepted
time: 764ms
memory: 139144kb
input:
200000 500000 126568 196936 9430 10915 35169 4802 158358 178385 6972 64394 195785 6516 25461 26599 4038 8053 139220 3544 56433 102992 10000 108418 160973 9148 19311 33007 10000 28585 149000 9409 79166 115331 9260 90520 149000 3196 115331 157352 999 123567 149000 6488 149000 172863 5282 30759 118996 ...
output:
4744411891211 5012680904894 1880454352016 106574956676 4448367361727 5115072109791 731839373300 4816597185649 422449205245 3407982925073 2242409016374 2242403017560 2982840925171 3307244980099 1177265318709 45894923678 1099429971393 3479343390442 103800362802 2003388858219 3142414351229 203090740387...
result:
ok 500000 numbers
Test #77:
score: 0
Accepted
time: 756ms
memory: 142280kb
input:
200000 500000 21455 192801 5941 145517 192801 5116 168363 192801 1460 34116 192801 7573 157046 198857 904 11006 107185 10000 23919 116612 8499 107441 192801 9761 116612 177368 5246 90719 116612 5872 26501 121790 10000 92183 193016 503 28988 192801 7265 138166 170541 2285 52274 167486 2755 64755 9292...
output:
352421514321 5688989047022 305687333436 6431068693441 2317259176716 4259592171561 3263650928500 6107707492824 4408608859908 3614989575024 5047633318413 518388905870 5208683356281 1829181665024 1493035890769 2821513371556 5058595446273 679937728688 3999776762320 2018164114826 393734169787 47149331386...
result:
ok 500000 numbers