QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201046 | #6673. Be Careful 2 | yllcm | AC ✓ | 2303ms | 297324kb | C++14 | 4.8kb | 2023-10-05 08:41:03 | 2023-10-05 08:41:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define mp make_pair
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 5e3 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n, m, k;
int tot1, tot2;
int ls1[N], ls2[N];
pii a[N];
void disc() {
for(int i = 1; i <= k; i++)ls1[++tot1] = a[i].FR;
for(int i = 1; i <= k; i++)ls2[++tot2] = a[i].SE;
sort(ls1 + 1, ls1 + 1 + tot1);
tot1 = unique(ls1 + 1, ls1 + 1 + tot1) - (ls1 + 1);
sort(ls2 + 1, ls2 + 1 + tot2);
tot2 = unique(ls2 + 1, ls2 + 1 + tot2) - (ls2 + 1);
for(int i = 1; i <= k; i++) {
a[i].FR = lower_bound(ls1 + 1, ls1 + 1 + tot1, a[i].FR) - ls1;
a[i].SE = lower_bound(ls2 + 1, ls2 + 1 + tot2, a[i].SE) - ls2;
}
return ;
}
vector<int> A[N];
int sum1[N][N], sum2[N][N], vis[N][N];
int calc2(int l, int r) {
int i6 = 166374059, res = 0;
auto _calc = [&](int r) {
int v1 = 1ll * r * (r + 1) % P, v2 = (2ll * r + 1) % P;
return 1ll * v1 * v2 % P * i6 % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int calc3(int l, int r) {
int i2 = 499122177, res = 0;
auto _calc = [&](int r) {
int v = 1ll * r * (r + 1) % P * i2 % P;
return 1ll * v * v % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int calc4(int l, int r) {
int i30 = 432572553, res = 0;
auto _calc = [&](int r) {
int v1 = 1ll * r * (r + 1) % P;
int v2 = (2ll * r + 1) % P;
int v3 = (3ll * r % P * r % P + 3ll * r % P - 1) % P;
return 1ll * v1 * v2 % P * v3 % P * i30 % P;
};
add(res, _calc(r)); sub(res, _calc(l - 1));
return res;
}
int Calc(int tv1, int td1, int tv2, int td2, int l, int r) {
int res = 0;
add(res, 1ll * tv1 * tv2 % P * calc2(l, r) % P);
add(res, 1ll * (1ll * tv1 * td2 % P + 1ll * tv2 * td1 % P) % P * calc3(l, r) % P);
add(res, 1ll * td1 * td2 % P * calc4(l, r) % P);
return res;
}
int calc(int x, int y, int z, int w) {
int res = 0;
x = ls1[x]; y = ls1[y]; z = ls2[z]; w = ls2[w];
int st = max(y - x + 2, w - z + 2);
vector<int> p = {st, y + 1, n - x + 1, w + 1, m - z + 1, min(n, m) + 1};
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
for(int i = 0; i < p.size(); i++) {
if(p[i] < st)continue;
if(p[i] > min(n, m))continue;
int tv1 = 1, td1 = 0, tv2 = 1, td2 = 0;
int l = p[i], r = p[i + 1] - 1;
if(l > r)continue;
(x - 1 < n - p[i] ? add(tv1, x - 1) : (add(tv1, n), sub(td1, 1)));
(y - p[i] + 1 > 0 ? (sub(tv1, (y + 1) % P), add(td1, 1)) : void());
(z - 1 < m - p[i] ? add(tv2, z - 1) : (add(tv2, m), sub(td2, 1)));
(w - p[i] + 1 > 0 ? (sub(tv2, (w + 1) % P), add(td2, 1)) : void());
add(res, Calc(tv1, td1, tv2, td2, l, r));
}
return res;
}
int px[N], py[N], posy[N];
int main() {
n = read(); m = read(); k = read();
for(int i = 1; i <= k; i++)a[i].FR = read(), a[i].SE = read();
disc();
for(int i = 1; i <= k; i++) {
vis[a[i].FR][a[i].SE] = 1;
sum1[a[i].FR][a[i].SE] = 1;
sum2[a[i].FR][a[i].SE] = 1;
}
int ans = Calc(n + 1, P - 1, m + 1, P - 1, 1, min(n, m));
sort(a + 1, a + 1 + k);
iota(px + 1, px + 1 + k, 1);
sort(px + 1, px + 1 + k, [&](int x, int y) {return a[x].FR < a[y].FR;});
iota(py + 1, py + 1 + k, 1);
sort(py + 1, py + 1 + k, [&](int x, int y) {return a[x].SE < a[y].SE;});
for(int i = 1; i <= k; i++)sub(ans, calc(a[i].FR, a[i].FR, a[i].SE, a[i].SE));
for(int i = 1; i <= k; i++)posy[py[i]] = i;
for(int i = 1; i <= k; i++) {
vector<int> vis(k + 1), L(k + 1), R(k + 1);
for(int j = i; j <= k; j++)vis[posy[px[j]]] = true;
for(int j = 1; j <= k; j++)L[j] = j - 1, R[j] = j + 1;
auto del = [&](int x) {
int tl = L[x], tr = R[x];
if(tl)R[tl] = tr;
if(tr <= k)L[tr] = tl;
return ;
};
for(int j = 1; j <= k; j++)if(!vis[j])del(j);
for(int j = k; j >= i; j--) {
int nl = min(posy[px[i]], posy[px[j]]), nr = max(posy[px[i]], posy[px[j]]);
if(R[nl] == nr) {
add(ans, calc(a[px[i]].FR, a[px[j]].FR, a[py[nl]].SE, a[py[nr]].SE));
if(L[nl])sub(ans, calc(a[px[i]].FR, a[px[j]].FR, a[py[L[nl]]].SE, a[py[nr]].SE));
if(R[nr] <= k)sub(ans, calc(a[px[i]].FR, a[px[j]].FR, a[py[nl]].SE, a[py[R[nr]]].SE));
if(L[nl] && R[nr] <= k)add(ans, calc(a[px[i]].FR, a[px[j]].FR, a[py[L[nl]]].SE, a[py[R[nr]]].SE));
}
del(posy[px[j]]);
}
}
printf("%d\n", ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7960kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 8248kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 1ms
memory: 8004kb
input:
6 6 5 4 1 3 2 2 4 1 5 5 3
output:
161
result:
ok 1 number(s): "161"
Test #4:
score: 0
Accepted
time: 1ms
memory: 10220kb
input:
15 38 6 12 6 7 15 2 18 3 19 4 2 14 29
output:
80066
result:
ok 1 number(s): "80066"
Test #5:
score: 0
Accepted
time: 1ms
memory: 10072kb
input:
5145 5419 9 547 285 294 284 375 385 217 857 348 925 14 274 3104 853 184 953 794 603
output:
334363567
result:
ok 1 number(s): "334363567"
Test #6:
score: 0
Accepted
time: 1ms
memory: 8232kb
input:
5 5 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4
output:
25
result:
ok 1 number(s): "25"
Test #7:
score: 0
Accepted
time: 0ms
memory: 10032kb
input:
9145 9419 12 123 456 223 456 547 285 294 284 375 385 217 857 348 925 14 274 1104 853 184 953 794 603 2234 5678
output:
921360185
result:
ok 1 number(s): "921360185"
Test #8:
score: 0
Accepted
time: 1ms
memory: 8004kb
input:
6 8 4 2 3 3 3 4 2 1 1
output:
444
result:
ok 1 number(s): "444"
Test #9:
score: 0
Accepted
time: 105ms
memory: 155728kb
input:
1000000000 1000000000 5000 1657 1 1644 1 1000000 116362 1186 1 2392 1 1560 1 995 1 2340 1 1916 1 2143 1 1762 1 1000000 116109 1651 1 1000000 116059 2289 1 1000000 115730 1000000 115896 1000000 116499 1608 1 342 1 1000000 116949 1965 1 1000000 114571 1000000 116602 2171 1 1000000 114848 1000000 11627...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #10:
score: 0
Accepted
time: 103ms
memory: 156060kb
input:
1000000000 1000000000 5000 1 2581 1 2273 115983 1000000 116105 1000000 114552 1000000 1 1955 1 2254 116061 1000000 116182 1000000 115783 1000000 114564 1000000 116614 1000000 116229 1000000 116087 1000000 114956 1000000 1 2453 114766 1000000 115750 1000000 115448 1000000 1 1748 116665 1000000 1 2237...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #11:
score: 0
Accepted
time: 141ms
memory: 106712kb
input:
1000000000 1000000000 5000 824 1 811 1 2300000 114696 353 1 1559 1 727 1 162 1 1507 1 1083 1 1310 1 929 1 1000000 116109 818 1 1000000 116059 1456 1 1000000 115730 1000000 115896 2300000 114833 775 1 2300000 115576 2300000 115283 1132 1 1000000 114571 2300000 114936 1338 1 1000000 114848 2300000 114...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #12:
score: 0
Accepted
time: 122ms
memory: 106508kb
input:
1000000000 1000000000 5000 1 1748 1 1440 115983 1000000 116105 1000000 114552 1000000 1 1122 1 1421 116061 1000000 114516 2300000 115783 1000000 114564 1000000 114948 2300000 114563 2300000 116087 1000000 114956 1000000 1 1620 114766 1000000 115750 1000000 115448 1000000 1 915 114999 2300000 1 1404 ...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #13:
score: 0
Accepted
time: 137ms
memory: 8180kb
input:
1000000000 1000000000 5000 2300000 115622 1000000 116216 1000000 116852 2300000 115827 2300000 116715 1000000 116212 2300000 116390 2300000 114646 1000000 114857 2300000 116404 1000000 116398 1000000 115409 2300000 115721 1000000 116136 2300000 114925 2300000 114869 2300000 116176 1000000 115774 100...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #14:
score: 0
Accepted
time: 129ms
memory: 155792kb
input:
1000000000 1000000000 5000 116495 1000000 116269 1000000 115204 2300000 115724 1000000 116508 1000000 115095 2300000 116712 1000000 114789 2300000 115009 2300000 114795 1000000 115093 2300000 115612 1000000 116183 2300000 116140 2300000 116148 2300000 115608 2300000 115111 1000000 115058 1000000 115...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #15:
score: 0
Accepted
time: 140ms
memory: 8436kb
input:
999999992 999999990 5000 1035170 5702575 3959104 3959104 3887901 7432303 11377527 9794948 6282049 47695 11781994 2037659 11292228 47695 6787467 878630 10441683 5492431 1240650 1129736 5631557 11377527 4863442 5631557 6662382 4863442 8837935 7070049 8837935 10441683 4878561 5702575 5610718 2664505 58...
output:
892807048
result:
ok 1 number(s): "892807048"
Test #16:
score: 0
Accepted
time: 2299ms
memory: 297172kb
input:
999999948 999999898 5000 6033860 10854965 57219333 28077882 18498300 33290576 34559919 16960059 40765867 73389700 9985342 17984966 54717579 26853732 13059544 23513592 56562634 27758141 19776481 35613289 6632028 11929378 14942564 7329745 7337824 13208993 33584464 60460021 13330979 6539654 32561958 58...
output:
461431823
result:
ok 1 number(s): "461431823"
Test #17:
score: 0
Accepted
time: 2303ms
memory: 297212kb
input:
999999524 999999758 5000 28630401 15905366 49821653 27672863 52823763 29343863 14406464 29362320 3914600 2178863 15379626 31340404 2382937 4856861 26445243 14692595 15255307 8475517 23233725 12911959 8922530 4954657 80413834 44658470 59845170 33233185 38234833 21236207 48814787 27111180 7919671 4397...
output:
811760775
result:
ok 1 number(s): "811760775"
Test #18:
score: 0
Accepted
time: 121ms
memory: 157988kb
input:
999999991 999999996 5000 191981012 91509738 114514 75994027 113271868 114514 191981012 74412508 73311176 114514 55237456 114514 157017806 114514 114514 38589289 114514 48208495 50968309 114514 151891598 191981012 34509833 191981012 112566922 191981012 54162112 191981012 99866720 114514 191981012 404...
output:
477858401
result:
ok 1 number(s): "477858401"
Test #19:
score: 0
Accepted
time: 118ms
memory: 158268kb
input:
999999997 999999992 5000 157493349 191981012 191981012 739725 191981012 103830381 191981012 56086190 163612413 114514 191981012 56630806 191981012 56513816 170698088 114514 97262819 114514 130313445 191981012 114514 113985965 114514 112636345 114514 76391763 114514 36458624 114514 35952358 114514 33...
output:
109114433
result:
ok 1 number(s): "109114433"
Test #20:
score: 0
Accepted
time: 120ms
memory: 149700kb
input:
999999999 999999992 5000 114514 21049898 101232053 191981012 114514 14704290 114514 85418326 191981012 17641251 90959749 191981012 114514 48586425 114514 85286676 114514 85318864 180324603 191981012 73453197 114514 191981012 96571986 191981012 42295145 114514 113760745 166197584 191981012 129916604 ...
output:
239360106
result:
ok 1 number(s): "239360106"
Test #21:
score: 0
Accepted
time: 0ms
memory: 10172kb
input:
100 100 40 13 77 15 17 74 83 25 51 49 65 60 19 83 86 71 87 47 2 7 31 34 65 84 32 58 69 89 92 67 61 49 79 92 74 76 87 96 37 45 21 56 84 53 72 16 30 59 41 55 9 31 72 86 53 95 53 80 87 51 99 55 83 13 93 3 90 61 83 65 27 66 57 52 34 3 46 6 30 92 80
output:
12252760
result:
ok 1 number(s): "12252760"
Test #22:
score: 0
Accepted
time: 3ms
memory: 14252kb
input:
100 100 100 91 50 58 1 93 95 58 77 32 60 36 77 18 3 67 33 25 6 23 77 69 2 24 77 96 17 50 99 81 22 22 46 88 54 50 18 74 40 4 38 77 3 2 7 98 37 14 98 68 33 13 23 17 51 40 63 43 58 27 76 77 19 48 73 14 92 27 72 63 33 33 54 98 96 47 2 49 37 36 85 5 43 23 69 5 19 78 98 99 91 48 12 26 51 11 90 93 31 27 26...
output:
4466541
result:
ok 1 number(s): "4466541"
Test #23:
score: 0
Accepted
time: 3ms
memory: 14564kb
input:
100 100 500 87 54 94 64 78 54 80 11 74 87 84 2 72 96 8 8 19 29 3 78 62 38 28 44 60 14 56 81 91 57 64 33 75 35 98 8 26 65 87 81 94 63 86 96 1 4 74 69 90 71 96 33 13 97 97 68 52 61 50 84 27 20 22 31 7 36 15 18 17 41 49 64 13 63 18 5 57 62 38 66 54 65 35 5 62 29 2 30 21 30 83 44 40 22 29 11 83 11 30 69...
output:
550657
result:
ok 1 number(s): "550657"
Test #24:
score: 0
Accepted
time: 22ms
memory: 14372kb
input:
100 100 1500 74 35 31 76 66 71 12 96 74 92 68 67 3 4 86 29 60 40 24 12 50 11 19 20 51 95 3 14 85 64 22 60 79 18 28 48 60 70 20 88 37 23 8 75 92 46 91 13 39 18 91 88 77 47 16 96 34 58 18 44 39 70 33 21 99 99 56 27 70 32 71 32 73 98 33 51 10 35 41 29 5 70 24 44 84 51 53 71 78 33 14 55 7 25 71 1 85 24 ...
output:
142410
result:
ok 1 number(s): "142410"
Test #25:
score: 0
Accepted
time: 62ms
memory: 16552kb
input:
100 100 3000 18 46 35 86 98 87 79 87 56 43 87 40 7 74 41 65 81 42 58 82 20 94 85 97 94 68 64 27 67 19 71 58 51 85 19 55 29 17 27 52 54 24 35 22 85 61 88 83 94 59 62 3 32 97 36 29 57 99 79 62 42 23 39 12 61 44 67 21 72 17 52 66 99 40 36 25 80 51 68 3 15 15 59 20 35 75 16 5 86 93 83 6 41 33 99 2 31 98...
output:
63891
result:
ok 1 number(s): "63891"
Test #26:
score: 0
Accepted
time: 139ms
memory: 14548kb
input:
100 100 4999 90 57 24 41 25 59 46 59 16 49 17 15 88 89 56 25 18 8 74 30 68 34 75 37 58 74 72 19 40 23 54 81 3 95 9 75 85 57 8 40 45 30 96 13 63 63 27 51 40 26 56 9 39 12 7 63 66 17 11 37 44 26 79 99 65 34 49 77 70 46 38 48 31 69 44 19 82 80 2 84 30 68 6 94 85 65 97 56 19 34 14 21 26 80 29 58 34 20 5...
output:
34812
result:
ok 1 number(s): "34812"
Test #27:
score: 0
Accepted
time: 139ms
memory: 14572kb
input:
100 100 5000 4 96 13 14 29 98 17 27 5 49 98 22 15 87 23 15 17 67 97 30 49 6 45 98 70 70 90 2 98 5 65 17 63 43 41 26 76 82 30 48 52 4 26 53 73 67 71 92 59 36 33 46 15 14 98 27 55 69 98 52 50 17 69 25 82 95 49 28 87 10 98 36 8 82 16 97 32 18 10 30 47 33 30 88 33 93 92 85 9 3 31 89 27 20 38 76 88 64 58...
output:
34455
result:
ok 1 number(s): "34455"
Test #28:
score: 0
Accepted
time: 0ms
memory: 14072kb
input:
100 2000 40 82 172 10 1709 49 504 80 1874 54 1543 65 1552 68 1116 89 501 62 1279 36 1385 36 1027 78 1662 58 1031 17 545 68 875 93 1837 56 1758 27 1845 46 1007 57 721 35 1153 77 76 18 889 68 27 49 863 15 885 72 264 88 1747 28 1808 26 1265 94 1838 21 1947 71 1220 51 709 80 491 34 1121 29 1878 57 638 4...
output:
476630897
result:
ok 1 number(s): "476630897"
Test #29:
score: 0
Accepted
time: 2ms
memory: 10312kb
input:
100 2000 100 64 1327 7 1857 34 130 52 998 50 122 98 1720 90 15 37 305 66 1956 97 1335 5 1223 98 717 94 182 18 931 58 159 92 1212 47 815 23 59 87 1735 76 133 98 1397 45 17 87 1529 16 1071 87 1722 56 645 17 408 34 1599 96 1684 16 843 35 1245 62 1630 38 539 4 598 92 849 92 1424 68 892 5 1304 66 103 94 ...
output:
874863095
result:
ok 1 number(s): "874863095"
Test #30:
score: 0
Accepted
time: 4ms
memory: 14436kb
input:
100 2000 500 60 1213 50 1837 19 1974 70 1136 92 1979 54 1180 49 211 76 1898 56 536 85 1091 6 118 3 254 66 393 28 1889 72 72 27 1122 35 112 75 616 44 1378 60 69 28 806 37 929 94 735 76 1146 5 707 40 1638 8 1900 90 760 18 135 43 1519 85 775 28 579 36 935 4 1458 46 1499 8 1613 82 540 75 1700 74 210 96 ...
output:
545166322
result:
ok 1 number(s): "545166322"
Test #31:
score: 0
Accepted
time: 15ms
memory: 16952kb
input:
100 2000 1500 49 1888 86 1376 46 856 79 17 45 697 92 1752 52 1378 63 1442 7 882 71 1370 96 702 52 497 93 897 74 249 63 1655 80 90 46 1904 27 371 15 1265 92 214 89 1812 87 719 45 823 15 1708 3 827 99 850 63 1180 6 401 87 124 77 32 2 377 85 627 40 169 14 281 14 1101 12 314 14 447 19 1781 51 626 90 745...
output:
148961647
result:
ok 1 number(s): "148961647"
Test #32:
score: 0
Accepted
time: 44ms
memory: 14708kb
input:
100 2000 3000 93 1277 2 1750 66 1555 38 1627 23 1251 4 332 68 266 18 1078 24 1386 6 1444 70 673 28 806 28 629 31 456 42 1407 26 545 22 1643 27 409 79 1991 95 394 94 1614 15 680 26 399 20 86 66 94 75 306 18 345 30 836 46 1023 11 1655 26 513 77 1336 72 588 86 505 38 274 98 96 34 691 84 627 2 1788 53 1...
output:
56815774
result:
ok 1 number(s): "56815774"
Test #33:
score: 0
Accepted
time: 108ms
memory: 15276kb
input:
100 2000 4999 69 141 90 319 92 570 13 503 74 817 41 1656 33 1735 29 1366 52 419 26 1608 15 417 17 1193 91 1056 31 1797 18 544 5 1792 81 1881 12 255 24 1177 75 1534 96 277 84 1562 8 1665 49 91 13 120 72 953 29 539 96 1831 51 1903 50 1843 27 1337 22 1178 73 307 59 1951 28 1431 79 911 66 1530 89 969 5 ...
output:
29031348
result:
ok 1 number(s): "29031348"
Test #34:
score: 0
Accepted
time: 102ms
memory: 13056kb
input:
100 2000 5000 78 1655 79 1968 97 1538 75 1328 75 780 24 1025 64 1775 99 1319 59 877 49 705 95 597 83 921 9 523 49 367 76 553 28 1623 30 1616 52 145 23 296 98 662 5 249 6 1095 18 982 2 793 31 1941 49 1670 9 1596 88 467 40 1178 34 220 34 318 15 1014 98 130 64 465 56 1356 40 257 46 108 60 1406 54 373 9...
output:
28106075
result:
ok 1 number(s): "28106075"
Test #35:
score: 0
Accepted
time: 0ms
memory: 14204kb
input:
100 1000000000 40 91 906492795 44 220406215 46 697653054 57 115159754 41 410299001 2 856461372 11 829769415 19 154206891 87 111013909 2 558231357 53 227124152 8 25775632 77 819248359 66 956427714 23 438568455 40 885638653 93 953383697 97 674250396 91 168010516 71 425324837 84 679265396 92 438925795 ...
output:
308636238
result:
ok 1 number(s): "308636238"
Test #36:
score: 0
Accepted
time: 0ms
memory: 10236kb
input:
100 1000000000 100 13 107090664 57 269885036 71 253364299 23 124674877 34 158640158 34 212481096 97 96462559 5 905248661 7 721358783 36 406914955 93 304044767 10 758826649 86 870834795 22 78209124 95 821043354 15 747758089 79 209048751 10 92632533 40 167864124 54 140677453 8 260747605 32 673110337 3...
output:
15721069
result:
ok 1 number(s): "15721069"
Test #37:
score: 0
Accepted
time: 3ms
memory: 14488kb
input:
100 1000000000 500 9 884176880 92 685216500 60 349365908 33 909262376 80 346546370 90 933603462 52 93869530 44 694779448 96 634413542 16 534218862 98 895186467 18 257872364 50 304205239 24 979628465 10 212894893 61 705524564 66 695239491 58 881000335 1 718387750 29 744828497 37 746039846 17 96409865...
output:
732332250
result:
ok 1 number(s): "732332250"
Test #38:
score: 0
Accepted
time: 7ms
memory: 15104kb
input:
100 1000000000 1500 3 874996650 86 465478752 71 678518381 8 721100871 65 36660500 46 628307861 25 249070752 48 926487045 51 101624043 78 8109175 75 39868981 67 361110166 44 222180507 91 738700669 37 490125317 94 462382018 80 201684972 10 80444765 15 309604275 37 731634425 5 810314270 24 229206345 47...
output:
753671314
result:
ok 1 number(s): "753671314"
Test #39:
score: 0
Accepted
time: 34ms
memory: 14612kb
input:
100 1000000000 3000 46 315468771 89 795555094 87 273919299 75 763599031 39 557565439 69 561796240 29 858884876 98 867636821 76 947865397 13 149920455 45 960937190 30 581327774 82 994611919 48 695928933 27 814619938 41 453055204 57 78794097 97 664376126 79 381113636 39 183850392 13 863767314 52 77581...
output:
165068431
result:
ok 1 number(s): "165068431"
Test #40:
score: 0
Accepted
time: 88ms
memory: 15812kb
input:
100 1000000000 4999 23 981436455 78 697469606 14 778058249 45 580983878 98 690859674 94 768219874 7 799618639 14 218210131 9 313076636 33 658739035 97 571652795 20 699689049 43 479246235 49 563485912 99 130776916 32 135723448 17 658033163 90 77170696 28 663286691 28 383151393 4 26990484 21 856223099...
output:
162258766
result:
ok 1 number(s): "162258766"
Test #41:
score: 0
Accepted
time: 87ms
memory: 14800kb
input:
100 1000000000 5000 28 127064660 67 990623740 19 94387764 21 184315217 94 518385844 85 794171229 37 583105000 84 199077103 4 549302796 56 626057952 70 523247708 86 920946496 59 996375805 66 707676893 58 418428414 39 518883170 65 402514408 23 581452060 23 804453957 39 532845441 24 729930201 46 445780...
output:
493451776
result:
ok 1 number(s): "493451776"
Test #42:
score: 0
Accepted
time: 1ms
memory: 10448kb
input:
1000 100 40 815 84 52 18 361 39 621 81 492 73 694 1 88 43 393 97 369 21 758 85 905 68 461 73 392 45 866 32 26 96 816 17 858 49 828 10 976 41 169 91 327 82 669 20 796 50 559 24 314 82 547 14 473 74 715 77 235 76 896 15 548 34 451 80 387 97 223 49 713 17 828 57 758 70 103 64 687 39 560 85
output:
258922145
result:
ok 1 number(s): "258922145"
Test #43:
score: 0
Accepted
time: 2ms
memory: 14620kb
input:
1000 100 100 490 7 149 93 485 65 309 82 31 86 267 56 687 1 711 65 877 66 417 19 871 45 652 43 430 42 777 45 486 45 764 99 690 73 446 68 850 41 470 62 805 93 510 89 32 97 482 84 300 38 60 74 861 8 828 32 790 24 913 38 847 81 229 19 393 39 492 55 379 58 503 57 398 1 700 27 916 21 888 72 28 25 382 3 26...
output:
887311204
result:
ok 1 number(s): "887311204"
Test #44:
score: 0
Accepted
time: 0ms
memory: 28720kb
input:
1000 100 500 834 15 787 54 830 24 187 21 541 10 188 68 772 94 979 37 177 85 369 20 99 85 552 14 115 40 234 22 814 81 72 95 921 53 804 50 74 66 675 5 69 54 279 80 444 68 420 47 885 84 414 72 983 45 628 41 938 28 810 46 630 81 549 75 102 82 412 4 234 66 672 70 394 76 784 21 421 50 943 57 994 35 601 33...
output:
127131287
result:
ok 1 number(s): "127131287"
Test #45:
score: 0
Accepted
time: 15ms
memory: 57216kb
input:
1000 100 1500 603 80 292 38 376 94 475 36 688 75 225 80 775 94 369 70 191 9 73 82 242 78 707 8 914 67 600 54 651 80 482 12 616 95 320 62 775 40 75 63 141 93 33 14 943 88 432 88 136 8 766 13 638 19 840 4 644 22 169 65 919 74 836 19 295 75 247 72 627 25 213 17 840 38 144 99 584 43 618 8 557 4 129 50 8...
output:
27193936
result:
ok 1 number(s): "27193936"
Test #46:
score: 0
Accepted
time: 47ms
memory: 63840kb
input:
1000 100 3000 350 91 134 52 423 12 820 31 185 26 915 54 985 53 509 98 49 22 566 53 522 70 588 85 547 48 372 62 795 47 753 2 467 63 964 66 149 94 415 26 709 90 581 51 614 11 35 63 423 57 705 27 279 69 319 36 576 13 962 76 728 53 854 73 282 98 541 89 858 15 376 55 972 62 435 26 405 43 82 74 98 89 453 ...
output:
11057434
result:
ok 1 number(s): "11057434"
Test #47:
score: 0
Accepted
time: 125ms
memory: 65896kb
input:
1000 100 4999 641 94 258 7 643 83 270 3 811 31 813 24 707 76 570 61 239 80 817 96 917 17 785 24 875 50 120 51 8 46 930 33 464 73 748 82 377 28 162 14 861 84 358 46 20 10 299 22 159 20 298 41 758 83 124 67 388 21 422 56 593 60 831 61 421 88 181 54 664 40 42 30 419 83 200 21 759 67 737 57 698 39 305 7...
output:
5859428
result:
ok 1 number(s): "5859428"
Test #48:
score: 0
Accepted
time: 122ms
memory: 69936kb
input:
1000 100 5000 106 35 76 76 8 23 308 70 88 32 265 32 463 67 567 43 156 32 52 2 584 81 833 90 689 42 192 30 237 25 184 68 497 21 999 33 850 49 189 18 660 66 478 83 273 18 496 72 466 38 316 66 549 89 354 26 894 77 765 70 581 47 937 85 767 50 424 96 319 8 399 26 493 92 222 99 655 14 933 94 806 15 284 68...
output:
5722436
result:
ok 1 number(s): "5722436"
Test #49:
score: 0
Accepted
time: 0ms
memory: 10200kb
input:
1000 2000 40 64 701 722 362 64 1299 754 1805 380 616 566 1903 781 1619 903 1871 230 977 497 922 209 637 656 261 576 894 222 733 900 104 277 1872 523 1756 297 132 250 538 523 689 650 749 567 648 114 1231 311 1835 205 1980 18 371 919 665 920 274 46 908 40 1034 409 1476 319 1301 44 168 444 990 445 986 ...
output:
142200714
result:
ok 1 number(s): "142200714"
Test #50:
score: 0
Accepted
time: 2ms
memory: 12460kb
input:
1000 2000 100 684 1360 268 1574 85 1382 690 114 705 863 453 1825 15 201 919 559 579 944 970 1464 111 419 169 560 898 1549 453 1278 732 302 50 735 216 1223 617 1523 635 250 139 153 253 299 887 102 556 1217 765 301 772 70 533 806 961 1556 723 1040 800 1576 93 1307 342 1975 507 1802 783 864 225 1421 87...
output:
173515609
result:
ok 1 number(s): "173515609"
Test #51:
score: 0
Accepted
time: 4ms
memory: 32944kb
input:
1000 2000 500 108 1246 470 217 947 37 568 252 216 722 374 768 537 398 626 153 236 1522 405 411 855 1168 506 243 226 1614 347 91 418 70 793 938 446 666 538 227 858 1229 826 606 953 1561 701 497 968 277 703 1039 358 1200 405 1799 3 1195 86 571 431 1362 427 1837 481 1505 186 89 492 1260 144 428 22 1896...
output:
554189117
result:
ok 1 number(s): "554189117"
Test #52:
score: 0
Accepted
time: 17ms
memory: 53536kb
input:
1000 2000 1500 410 1420 794 1051 182 1573 884 1027 170 1309 828 1237 310 1854 239 389 499 1053 817 1610 981 803 391 750 415 63 33 560 348 1588 350 1615 235 45 762 1535 419 174 732 1593 488 1128 781 162 816 38 171 1544 813 250 16 1039 910 1947 955 350 512 1439 314 1188 810 877 838 95 90 549 932 1594 ...
output:
238838802
result:
ok 1 number(s): "238838802"
Test #53:
score: 0
Accepted
time: 59ms
memory: 66228kb
input:
1000 2000 3000 594 810 636 1425 310 936 25 1300 104 381 955 334 3 80 941 25 715 748 748 1539 342 257 273 1059 565 1794 242 104 492 822 826 1552 86 1930 888 92 792 900 509 1481 57 1594 250 1976 50 1614 649 1921 664 34 874 494 631 1113 791 785 801 1821 108 148 699 1013 294 141 951 821 788 1964 648 671...
output:
654807693
result:
ok 1 number(s): "654807693"
Test #54:
score: 0
Accepted
time: 135ms
memory: 63848kb
input:
1000 2000 4999 805 1010 323 1847 13 1950 37 1366 731 1283 417 1658 804 213 877 312 468 443 642 1848 737 664 470 1445 377 367 553 1962 703 1958 440 654 163 168 315 1419 21 1939 336 915 646 256 544 713 892 735 913 1409 961 1542 467 1805 31 1306 596 1263 738 1073 210 336 485 1691 271 500 92 687 865 126...
output:
793206926
result:
ok 1 number(s): "793206926"
Test #55:
score: 0
Accepted
time: 136ms
memory: 70048kb
input:
1000 2000 5000 832 1187 140 308 813 919 75 856 7 56 305 218 997 1588 438 411 822 239 314 946 966 35 80 1174 628 1834 62 532 933 1967 51 1294 989 1902 5 1163 493 1868 284 43 8 1418 664 393 226 198 673 629 706 1364 485 1859 821 364 469 417 682 494 910 712 473 818 582 1526 437 364 110 1778 109 418 47 1...
output:
597537195
result:
ok 1 number(s): "597537195"
Test #56:
score: 0
Accepted
time: 2ms
memory: 12572kb
input:
1000 1000000000 40 77 103727882 653 318241889 946 349212567 393 387746557 885 713394545 863 439584423 809 84023534 125 492837794 326 987465290 296 889547838 698 216417880 662 236899348 679 329988738 116 920708460 251 927778395 14 489733306 495 238693006 282 638590509 569 679174340 40 787268400 274 6...
output:
723916280
result:
ok 1 number(s): "723916280"
Test #57:
score: 0
Accepted
time: 0ms
memory: 14428kb
input:
1000 1000000000 100 618 526348331 775 100181278 816 708261363 293 993365232 551 369890766 112 882347154 346 89786899 513 579936592 685 536753990 148 210330348 234 442777116 454 549159447 491 379099400 96 394301462 115 192337929 462 981936402 661 375633818 769 847174570 479 566659166 543 799533412 94...
output:
346357608
result:
ok 1 number(s): "346357608"
Test #58:
score: 0
Accepted
time: 0ms
memory: 28668kb
input:
1000 1000000000 500 962 8467247 494 810480042 243 726115118 91 482985432 499 340977533 595 898436821 868 792226569 782 369467379 904 744776050 225 337634255 541 328886116 354 48205162 738 812469843 552 590688103 880 584189468 768 644735576 892 783676704 690 340575073 264 412150093 230 620503903 129 ...
output:
670463729
result:
ok 1 number(s): "670463729"
Test #59:
score: 0
Accepted
time: 9ms
memory: 57220kb
input:
1000 1000000000 1500 565 597119310 705 944900872 380 439122090 539 233695406 4 109762178 22 999884242 981 387467107 541 871838968 399 164310220 124 623159092 91 11151400 656 990020054 786 871634647 298 193779180 224 507996155 589 678921029 865 463293945 499 444952960 82 966633948 528 229262266 673 8...
output:
404642399
result:
ok 1 number(s): "404642399"
Test #60:
score: 0
Accepted
time: 40ms
memory: 63660kb
input:
1000 1000000000 3000 669 742624131 547 569944515 990 407638161 242 493013012 455 552519263 195 638405322 112 997281231 244 29808191 257 88699430 55 175035772 451 854071755 100 427057109 981 939033361 507 72859590 931 127458077 985 964561516 153 340403071 144 323851623 455 333110611 947 681478231 884...
output:
446439892
result:
ok 1 number(s): "446439892"
Test #61:
score: 0
Accepted
time: 111ms
memory: 69804kb
input:
1000 1000000000 4999 960 920378562 671 176891727 773 833629257 691 388545713 2 58928654 93 844828956 913 938014994 742 163562054 10 158943367 868 351936808 846 542935214 297 328598938 231 423667676 256 18564423 143 148647753 117 647229760 230 919642136 490 736646191 683 615283665 694 175746533 474 4...
output:
791232707
result:
ok 1 number(s): "791232707"
Test #62:
score: 0
Accepted
time: 104ms
memory: 69900kb
input:
1000 1000000000 5000 550 849187319 489 470045862 12 933139325 729 618761897 402 886454822 62 870780310 107 721501355 739 144429026 802 690136827 620 319255724 76 494530127 345 844823685 562 235764547 764 162755404 373 731266552 290 30389483 700 742271235 259 240927556 157 539631486 285 325440581 273...
output:
446268006
result:
ok 1 number(s): "446268006"
Test #63:
score: 0
Accepted
time: 0ms
memory: 14200kb
input:
1000000000 100 40 21614929 93 461614784 91 163670262 33 72329990 4 199472984 67 197079615 75 161450122 26 153888336 40 181669402 73 949917941 43 349622219 24 685955706 99 639790680 46 896317931 82 86939246 1 197769492 46 18406347 85 188847409 77 544939792 95 95989928 97 433612971 86 189176572 10 792...
output:
278181899
result:
ok 1 number(s): "278181899"
Test #64:
score: 0
Accepted
time: 0ms
memory: 16644kb
input:
1000000000 100 100 703598234 33 679420696 99 459844259 42 247638096 23 531187439 11 514864276 86 928352439 15 226394771 40 582739114 74 691361549 56 619858990 44 446438993 79 435484645 5 571470252 60 932846928 62 869086232 35 34976846 25 283887384 96 557316443 38 783035519 18 380375287 49 707654671 ...
output:
907196240
result:
ok 1 number(s): "907196240"
Test #65:
score: 0
Accepted
time: 3ms
memory: 36832kb
input:
1000000000 100 500 37676728 40 146304984 55 922483582 96 279700879 61 519173413 43 458465776 12 945276583 17 318599181 12 734389968 97 605826684 61 446655594 76 593979204 46 221328700 2 904100825 41 301499593 7 845719367 22 435265824 5 38917958 78 70851618 72 900316808 56 287897041 10 762155928 97 3...
output:
578434571
result:
ok 1 number(s): "578434571"
Test #66:
score: 0
Accepted
time: 14ms
memory: 98188kb
input:
1000000000 100 1500 539057299 25 510373193 5 957916743 60 215142360 11 208555244 78 186174891 11 689332299 48 714137024 63 643512474 63 814835521 8 976255879 73 894866044 82 858458026 80 809317325 71 339769646 60 421218188 9 632900853 73 738164659 49 136957493 77 319831753 95 376397381 89 17535660 6...
output:
547189117
result:
ok 1 number(s): "547189117"
Test #67:
score: 0
Accepted
time: 40ms
memory: 186376kb
input:
1000000000 100 3000 57962185 36 521003394 18 884142201 77 915136367 6 587440993 29 29679590 92 512518500 12 320514743 95 690210025 65 489515660 74 981468379 70 808650664 60 41379556 66 989065606 79 370937671 15 430081150 8 264347706 40 880294951 56 948905588 24 503869746 59 369878599 98 769442112 11...
output:
692562099
result:
ok 1 number(s): "692562099"
Test #68:
score: 0
Accepted
time: 111ms
memory: 297100kb
input:
1000000000 100 4999 641497714 47 138715189 72 78068864 53 373170967 77 892394361 38 208598953 59 111383758 35 542988108 59 581128968 32 145563849 22 563420803 9 923010307 99 705334747 72 459796154 72 565362184 23 571174529 31 381906027 51 629899942 85 62577469 53 954487986 46 670031173 91 885616036 ...
output:
206304920
result:
ok 1 number(s): "206304920"
Test #69:
score: 0
Accepted
time: 103ms
memory: 297048kb
input:
1000000000 100 5000 330788761 87 32259569 46 834461952 87 110241555 36 864985635 39 50136980 66 137121750 25 885426761 41 284880867 78 870719640 26 656935379 85 618848463 65 162700693 68 275991214 55 539179702 5 993776757 66 715491578 7 300254687 28 131748344 82 261829365 54 363921950 69 592819326 4...
output:
567850893
result:
ok 1 number(s): "567850893"
Test #70:
score: 0
Accepted
time: 0ms
memory: 8404kb
input:
1000000000 2000 40 328732610 1533 240893236 939 813513894 1157 288361777 783 322906279 1237 684440391 1266 550243021 936 243022320 422 360082346 1876 740173768 240 472935397 1883 763395160 1670 233721194 1408 6866945 1251 307911386 1961 845276578 1195 352623714 1587 309858675 1457 432223498 3 920362...
output:
712672083
result:
ok 1 number(s): "712672083"
Test #71:
score: 0
Accepted
time: 2ms
memory: 14588kb
input:
1000000000 2000 100 775977785 444 724755135 1604 574357395 413 722812396 774 508222374 968 496026832 639 663076820 1826 615109826 1646 781290384 1033 74221336 1236 662897295 1241 582339782 1552 164300426 208 394029319 666 48828959 261 432708253 901 221702063 243 369325646 1541 894774259 1708 9579480...
output:
342614501
result:
ok 1 number(s): "342614501"
Test #72:
score: 0
Accepted
time: 0ms
memory: 36888kb
input:
1000000000 2000 500 893236832 330 191639423 1583 36996719 259 459907879 912 791175648 680 66513179 1435 680000964 23 785462090 1094 227908539 1612 693719170 183 567841753 282 729879994 1752 950144480 418 648512038 961 495629477 1510 409341388 811 916958341 1022 419323520 99 191489988 835 75229352 11...
output:
729935351
result:
ok 1 number(s): "729935351"
Test #73:
score: 0
Accepted
time: 8ms
memory: 98528kb
input:
1000000000 2000 1500 55713573 722 15614544 819 249168742 151 306845971 365 465597217 642 499128297 1936 866644038 1364 498491504 1920 293211816 728 264794489 1886 296394246 860 645940372 196 473550777 412 656415813 1817 966815938 1612 59604338 396 956080226 454 574130949 210 41702266 321 555491627 1...
output:
837878018
result:
ok 1 number(s): "837878018"
Test #74:
score: 0
Accepted
time: 38ms
memory: 184668kb
input:
1000000000 2000 3000 984683856 112 26244745 1047 175394200 996 711872679 639 549515666 1713 637600296 516 984797539 1296 809901921 1410 966794213 569 644507327 1814 596574046 168 559724992 650 361505005 1997 131131395 25 997983963 1364 146615154 997 214411925 194 11228542 248 263715761 1710 11264477...
output:
127347397
result:
ok 1 number(s): "127347397"
Test #75:
score: 0
Accepted
time: 105ms
memory: 295464kb
input:
1000000000 2000 4999 941334541 975 938923839 1615 369320862 156 169907279 704 854469034 469 521552359 358 288695497 1722 32375287 1697 857713156 1454 517374963 788 961707023 58 752232489 1037 103608052 1380 680009796 1220 270556331 1837 582675833 99 410118100 431 838981386 1947 750502795 896 2682957...
output:
747741505
result:
ok 1 number(s): "747741505"
Test #76:
score: 0
Accepted
time: 105ms
memory: 295844kb
input:
1000000000 2000 5000 925592888 489 832468219 1412 125713952 833 280093021 194 43879756 1096 658057686 917 392581343 952 669781241 1796 561465055 60 242530754 1884 272041045 92 369922792 619 482826143 555 496204856 1789 461193295 1846 927130207 1929 665555796 167 431188277 1983 741525817 162 79245653...
output:
857804518
result:
ok 1 number(s): "857804518"
Test #77:
score: 0
Accepted
time: 0ms
memory: 14136kb
input:
1000000000 1000000000 40 721000297 752272409 685488581 920220980 298337630 592825837 426516997 87159395 359055567 536870279 126087969 464660004 546821615 746967842 265381300 405501965 614587336 930082327 960685523 222793049 974661504 891501692 354869824 446143492 608245678 837038323 114096841 933588...
output:
266954901
result:
ok 1 number(s): "266954901"
Test #78:
score: 0
Accepted
time: 2ms
memory: 14168kb
input:
1000000000 1000000000 100 612842256 807720481 196970815 29285486 238553189 10838241 353932766 443678370 183681332 579774218 41735320 810109534 238236755 297498419 246712249 386436384 487914569 184479924 374113109 47977961 874436721 473786067 770498946 286982738 488505226 856316247 121865672 68475306...
output:
701848163
result:
ok 1 number(s): "701848163"
Test #79:
score: 0
Accepted
time: 7ms
memory: 38944kb
input:
1000000000 1000000000 500 25068604 289839398 663855103 366469096 701192513 106839850 307847695 523233170 466634606 845828285 395402220 904347055 960193598 999938089 633883958 254115025 639565423 392501983 915463089 880314567 701233324 769960467 701219712 786028452 352497135 662801845 454496244 88113...
output:
635279564
result:
ok 1 number(s): "635279564"
Test #80:
score: 0
Accepted
time: 20ms
memory: 100168kb
input:
1000000000 1000000000 1500 966796879 512961013 732119526 294054610 353473681 284190803 325061104 754537059 291982200 422650216 188284231 267816297 755330891 333233654 107824794 437418474 529876589 738643703 606116546 761913204 124628036 991683710 262839713 768246902 325699903 266755149 306032820 338...
output:
193782150
result:
ok 1 number(s): "193782150"
Test #81:
score: 0
Accepted
time: 63ms
memory: 184436kb
input:
1000000000 1000000000 3000 895767164 658465833 742749727 919098251 357846993 174559021 730087812 797035219 592720095 943555155 326756230 123156823 795336538 238015079 714202512 968502849 871541441 879852359 280796685 608757183 207988390 129571367 471591633 578399111 508621431 334153862 485781101 512...
output:
591602486
result:
ok 1 number(s): "591602486"
Test #82:
score: 0
Accepted
time: 151ms
memory: 297140kb
input:
1000000000 1000000000 4999 852417848 619400818 360461522 604193317 473625801 678697971 483089711 909387366 897673463 76849391 210708293 34613157 472349650 588814241 936675877 24108860 467493084 28244152 641877574 707510365 494973513 740286971 664099130 401793086 250724478 740640322 34659502 16306486...
output:
70444985
result:
ok 1 number(s): "70444985"
Test #83:
score: 0
Accepted
time: 153ms
memory: 297324kb
input:
1000000000 1000000000 5000 541708896 843176876 254005902 819199598 230018890 700060184 925192998 139603551 870264737 904375560 642180920 138712365 203120342 962235202 279114531 4975832 466212283 481289757 662000665 674829282 805307534 770029738 986822132 623050533 629942569 335917747 850854562 30725...
output:
23338781
result:
ok 1 number(s): "23338781"