QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212401 | #1974. Black Family Tree | Zanite# | AC ✓ | 51ms | 15348kb | C++17 | 1.7kb | 2023-10-13 15:37:23 | 2023-10-13 15:37:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
#define All(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << (x) << '\n';
const int iINF = 1'000'000'000;
const ll INF = 1'000'000'000'000'000'000;
struct FenwickTree {
int n;
vector<ll> BIT;
FenwickTree(int n) : n(n) {
BIT.assign(n+1, 0);
}
void update(int idx, ll val) {
for (; idx <= n; idx += (idx & -idx)) {
BIT[idx] += val;
}
}
ll sum(int idx) {
ll ret = 0;
for (; idx > 0; idx -= (idx & -idx)) {
ret += BIT[idx];
}
return ret;
}
ll query(int l, int r) {
return sum(r) - sum(l-1);
}
};
const int maxN = 100'023;
int N, Q;
ll C[maxN];
vector<int> children[maxN];
vector<pii> queries[maxN];
ll ans[maxN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> Q;
for (int i = 1; i <= N; i++) cin >> C[i];
for (int p, i = 2; i <= N; i++) {
cin >> p;
children[p].push_back(i);
}
for (int l, r, i = 1; i <= Q; i++) {
cin >> l >> r;
queries[l].push_back({r, i});
}
FenwickTree F(N);
for (int i = N; i >= 1; i--) {
ll cur = C[i];
for (auto c : children[i]) {
ll tmp = F.query(c, c);
cur += tmp;
F.update(c, -tmp);
}
F.update(i, cur);
// cout << i << " " << cur << '\n';
for (auto [j, idx] : queries[i]) {
ans[idx] = F.query(i, j);
}
}
for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8364kb
input:
6 5 1 2 4 8 16 32 1 2 2 1 5 1 1 2 3 4 5 2 6 6 6
output:
63 14 56 62 32
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 8392kb
input:
5 25 4723 3513 2046 6286 9584 1 2 2 1 1 5 5 5 2 3 2 3 4 4 2 4 2 2 1 2 2 5 3 3 2 2 1 3 2 4 1 5 2 2 3 3 3 5 2 5 1 3 1 5 2 3 4 5 4 4 4 4 1 3
output:
26152 9584 11845 11845 6286 11845 11845 26152 21429 2046 11845 26152 11845 26152 11845 2046 17916 21429 26152 26152 11845 15870 6286 6286 26152
result:
ok 25 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 8416kb
input:
10 100 1457 936 8200 7604 1431 2726 6728 2545 3010 267 1 2 3 4 5 2 1 6 6 1 9 7 7 4 4 3 10 4 7 2 2 2 10 6 8 4 7 3 10 8 8 3 10 4 6 4 4 4 8 5 9 1 1 5 7 5 10 9 9 6 8 6 6 10 10 2 4 1 5 7 9 2 3 4 10 3 8 2 10 6 10 5 7 1 1 4 5 3 5 6 8 7 7 2 5 3 3 7 9 2 10 1 8 1 2 1 4 1 10 3 4 4 7 3 4 2 2 2 10 2 3 1 9 3 4 9 ...
output:
34904 6728 15038 32511 21766 30902 33447 15276 21766 32511 2545 32511 15038 15038 24311 16707 34904 14162 16707 3010 15276 6003 267 30902 34904 12283 30902 24311 32511 33447 15276 14162 34904 15038 23238 15276 6728 30902 23238 12283 33447 34904 34904 34904 34904 23238 21766 23238 30902 33447 30902 3...
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 8140kb
input:
20 400 3369 7577 2036 6800 9118 4011 4163 6177 7663 7722 8570 5139 5089 3187 9604 2154 9765 8074 4140 4101 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 3 4 10 16 5 12 8 10 10 11 14 16 13 13 20 20 14 14 8 15 7 19 6 6 5 13 16 16 10 19 2 3 4 15 3 5 18 18 7 16 2 16 8 13 20 20 13 13 3 18 10 10 17 20 5 7 8 8 1...
output:
107513 49706 98677 59400 24533 14945 5089 4101 3187 81385 85548 17720 98677 2154 67545 115090 105477 107513 8074 85548 115090 78198 4101 5089 107513 15963 26080 80742 17935 15963 107513 41465 11758 28234 107513 29672 105477 9765 11919 11758 51582 85548 67545 30159 3187 63450 118459 9604 98677 8570 2...
result:
ok 400 lines
Test #5:
score: 0
Accepted
time: 51ms
memory: 13736kb
input:
100000 100000 8029 7085 635 4300 6254 5928 4621 9793 9449 1053 5741 4135 7188 9600 5024 3024 9332 4417 6458 3033 4875 637 3280 3787 5535 9296 3390 4590 8158 5782 4977 8335 4453 5676 3484 9232 6052 214 5229 6335 1743 6960 9857 668 7712 6593 5491 579 553 1045 134 2072 9101 8502 9225 1930 5188 2631 864...
output:
2875897 4245113 7279182 484062622 51021802 100278165 2716542 323855818 69291 64093 455140 22310982 489033 12666804 32960004 1108250 6235193 366507450 5544535 54254936 21740405 8370 3738236 17471 347386358 338123464 1735828 8391 1633409 224525 1262580 338900101 29624 73125 50789 125592361 423584668 2...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 42ms
memory: 15292kb
input:
100000 100000 2837 9940 6030 9413 2600 1437 9829 4278 660 6655 1571 3167 9455 1012 624 6058 2888 2681 6266 5661 2924 2925 525 3784 6422 4426 3122 3346 9262 9090 9078 9875 4434 6453 4048 7730 3265 3097 3735 1822 7441 6978 2643 142 3811 7179 627 3262 915 2350 2838 2076 5504 7292 2160 4920 6323 3677 55...
output:
252075625 424640180 168263033 365597422 5107537 194173860 47709166 244547988 420622371 480844760 233641056 280175711 176385719 289402283 365597422 387317850 87569060 87695383 158282105 147000391 251735846 13362466 372398145 304918049 108236214 463911665 327070656 457701200 271544874 38385554 4226775...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 43ms
memory: 14540kb
input:
100000 100000 2217 4599 1781 2633 7215 3145 1595 6231 3666 3381 2902 2765 9352 4128 5422 7248 7477 6214 105 5573 6091 7665 2690 8922 8044 6424 2660 5648 2477 6464 5329 6348 3447 531 9448 4947 385 7299 7932 2159 2773 787 3285 4628 4268 4046 1066 6458 2550 5967 1537 6214 431 2177 897 2144 1061 8148 49...
output:
42056727 343471454 86920845 434593089 336848810 410693687 367325841 829 94242481 331724394 185324003 187389586 484335771 331158998 170081437 287076444 301520497 460887728 99663081 398054016 118649464 105824002 198914480 450634027 194114622 312494855 476823119 251856236 445963523 356674221 445273109 ...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 46ms
memory: 14496kb
input:
100000 100000 3330 2684 9505 1788 7762 1555 7299 1311 9070 5753 1803 1649 9908 1782 4265 4155 9271 5330 2891 4958 3990 9989 6849 4580 3557 7210 3554 1019 3260 5053 2924 8445 3555 1125 3295 3796 5247 5079 6960 9045 7781 6250 4245 2979 3744 3443 6544 6326 5747 4181 2494 5487 9818 9145 8968 2674 6614 4...
output:
455925202 497916458 239437822 284911588 298334363 349404398 306944779 477510599 298000757 284121476 231972359 450255191 473478371 379977393 321203700 158663101 459135896 492551730 340728296 22856 6217557 21969 24534 446693717 444377407 75494372 204148537 113502 199409773 249995310 355095295 26775969...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 39ms
memory: 14488kb
input:
100000 100000 9439 7509 1440 3290 5764 2288 7272 9935 8829 2265 4234 4521 5340 1178 4153 8438 2064 5838 1787 5892 7506 8496 7012 3652 7508 172 4355 5792 5285 5590 9830 4571 5025 8925 6598 3916 1821 3658 9564 2902 4197 2438 7836 7362 6476 8756 5820 5338 5936 3516 5921 2917 3607 5312 7477 7210 3643 47...
output:
178754251 451216332 48090942 176228328 378402089 359304759 483091919 351421777 321238634 166697977 308603123 456061287 274040439 268233428 468801678 4668 230716949 117169866 454934017 318021545 159873935 124761637 324156794 315694268 464157267 244519910 289772629 483518963 153390982 194929075 160572...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 46ms
memory: 14288kb
input:
100000 100000 4498 2035 6447 6899 6082 6418 8922 7792 40 8132 3023 9479 1556 3289 9826 1207 7528 8851 2162 8016 1321 8989 4365 9252 8920 6111 6487 4670 8730 167 6548 2956 5761 3301 6026 9691 9416 9294 9435 4893 202 6500 6545 1922 1534 2074 8935 7856 6912 8981 7955 3123 4621 8692 9590 6437 7674 4574 ...
output:
468520119 76153895 276514251 398392771 269276275 482153656 251318856 384731208 214552745 28830033 259407298 161328799 195818847 230970 123755761 416631 10908 163933096 120397 231534677 36152321 7520162 2252629 281431979 134925 398754890 146841970 65874643 387258424 498923061 80393611 232637285 50452...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 36ms
memory: 14272kb
input:
100000 100000 481 3990 2262 1859 3842 80 6880 9904 5165 7803 1717 7634 8456 7194 1210 7106 8234 9995 4989 261 7076 7070 1759 2045 1430 7733 8977 657 3804 9934 7426 1806 1484 8183 4261 6287 683 8689 4720 4656 3393 2015 7814 2614 5713 1500 2296 3805 1254 5849 2492 5007 1563 3105 8518 38 2193 6567 8251...
output:
449213911 378418899 229376594 400606470 92788861 378840809 391986393 32492136 308343876 108859587 298523480 66061853 341772882 497115838 249513310 350890283 479051053 460910577 419809446 191759170 488065044 208811259 27521060 24444 390956671 456833835 348775717 456646985 96626817 367782999 312402820...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 44ms
memory: 14300kb
input:
100000 100000 7965 435 6833 1508 9725 934 8354 5902 7805 734 9331 3838 5530 2444 4393 8447 697 6201 9185 2204 9494 502 655 1074 9368 7942 2019 9995 6281 774 9130 4266 3528 3837 821 2983 4675 4162 7257 4485 5299 7571 9321 1219 428 9785 3290 7367 6279 3162 4297 3312 58 2059 2568 6279 9293 2393 1235 75...
output:
467127118 273645111 20919 120740 313825778 474103967 303847786 172573339 292128288 382984981 430808735 459967743 186568264 321115170 170832314 469875733 212635975 31896 201044006 479231544 222573293 476284358 462001 194142838 187889696 26312407 211555589 122144437 440912653 353842713 19040 370953257...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 35ms
memory: 14252kb
input:
100000 100000 3705 9790 3829 2272 9072 3912 6047 735 5397 6061 1404 5904 8433 6863 5774 7902 655 3510 162 4091 8552 7651 7621 6178 4578 8060 3915 8371 7356 362 714 7251 5002 30 6959 3640 4726 1068 9383 4995 272 1046 4391 7059 1106 9753 1040 1998 1698 994 9940 9152 6481 5118 9777 1023 9619 535 1462 3...
output:
274178923 749685 327651229 180088 81262 433677171 366723718 184196453 2107 257031559 201413406 141216956 22863155 10469916 535917 54154767 2566 715367 279051 68165318 145889242 3146462 447977 338495421 434050402 494104201 14839 1402682 38845 20487037 1666398 130284 1090852 207808 177760 162490150 58...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 44ms
memory: 14212kb
input:
100000 100000 4713 1929 6029 95 5170 2051 6922 7206 5294 6707 8371 2292 2989 2798 9092 919 1235 104 7415 2683 8207 7386 5311 7220 4223 1224 8928 8332 2600 1635 4985 7194 3461 48 9814 3558 7168 8163 5927 5768 8903 9820 9416 8493 4740 1374 3854 5944 905 1875 140 7592 1854 8227 7811 4196 9050 5204 3142...
output:
117485217 424310292 95640483 484005487 394081824 182852132 260893307 260427115 279695082 42035 398067235 478464042 206055835 109634668 113149 367193511 347012087 66903 254463159 424205363 189956 423744469 93876 697020 236157404 389206652 364610328 343478071 490206304 837 348311304 194467924 48915707...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 46ms
memory: 14156kb
input:
100000 100000 2862 1881 3417 4971 1791 439 6840 2988 8650 1627 721 7430 6186 5686 5155 3129 5828 3812 1531 4396 5430 5980 1949 8864 2663 7794 9077 553 6655 2696 1484 9287 6573 3906 9387 6567 3464 3848 5727 8966 8003 7400 3061 1001 3150 2030 9758 1718 6192 3427 7402 5402 2758 4908 265 8106 2585 2180 ...
output:
101078 493064976 904993 353626473 114301412 76670 140273985 21897 399621 291103211 29064196 2032349 2685073 128489432 488962939 79410 1173835 3138784 1046423 13668265 210353 15262212 171101803 81254591 203725 1860177 489784218 36460785 297205198 9781 26835554 960173 73864699 471609220 19686609 78845...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 42ms
memory: 14296kb
input:
100000 100000 8952 3905 2563 6708 8824 7886 9759 881 3599 5216 3774 572 1973 3159 9887 9130 4638 6341 3423 4554 5913 3693 2524 7563 1981 8407 1388 6858 5550 5087 9350 3262 3118 3745 3746 8672 2633 3084 7153 8239 7681 7989 6456 2437 2588 6895 3054 225 3789 8980 6599 7674 1358 775 5824 2357 9170 5232 ...
output:
57357699 94998701 392710428 441020912 174462619 343937003 98458535 380564060 333738944 192492868 380939327 3368588 1304194 200160594 204684787 254131 202444631 446680043 58150 171955107 302866566 1156308 160655828 42396142 208113 1104677 411298830 427832868 163305336 460820865 218774180 51607495 550...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 37ms
memory: 15320kb
input:
100000 100000 8294 1143 9210 9413 3949 3314 5681 2669 925 4979 9227 1176 2580 8684 4881 6490 5060 4443 8391 1551 1926 8504 137 2571 2905 352 9607 2601 4198 90 5597 7057 4353 2887 2861 3235 7255 2489 7199 4945 5299 7696 3290 8671 5273 9577 9643 4420 3168 9271 9838 2352 8977 3007 1635 2740 3016 7869 5...
output:
175107345 94999826 262989707 211460426 324864848 312254814 492919227 422513071 253161973 377523761 483981771 162353137 169358579 445695381 353488576 360233328 179186826 142514091 113876448 488112124 315298443 232292463 248555344 111786726 150513553 7040884 375524186 321295354 305474727 297955294 184...
result:
ok 100000 lines
Test #18:
score: 0
Accepted
time: 32ms
memory: 15308kb
input:
100000 100000 2736 462 4620 3697 7113 2007 3531 6575 9094 4905 4047 779 8059 8850 8410 8870 5987 7601 3913 3940 8666 3667 4872 2440 6149 6099 838 1113 220 4432 6349 3911 4537 7517 5817 7671 7969 5208 6935 3868 2055 1405 2391 6296 9688 2903 3084 8654 6031 436 1169 5352 7079 1028 7360 5030 8180 8968 2...
output:
477074759 305508386 366088995 226706435 75520033 167489985 121316653 212720408 40777732 403438387 116120348 154864575 459404326 220276935 104532694 45195256 357747043 322765575 44115799 333313042 138855694 488455672 110763818 469568306 454753611 471385365 261262505 196391714 479880072 30715055 45791...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 47ms
memory: 15296kb
input:
100000 100000 2646 2692 979 4069 1353 5804 9757 8851 3766 9683 2380 8478 959 1996 2093 2567 9841 9882 6497 3763 4770 7835 2200 3416 5901 422 1656 1055 3269 431 2013 8363 6177 2593 6837 8025 6036 2340 6379 9062 1725 4528 8683 8125 3689 1701 824 7113 8486 828 1542 3634 9439 5653 1921 204 7903 8535 206...
output:
46765058 278504082 3858657 79012133 14916487 54251220 41207851 32462351 498745879 56116531 48707894 121027903 76777605 206854387 35379481 443404720 23115059 133483073 6925834 99432387 286428268 91452108 98458115 352141443 92094684 97826034 32228949 104704156 15126783 5646578 3787902 77136440 6232676...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 42ms
memory: 15284kb
input:
100000 100000 5092 3914 7801 3962 3273 1408 8691 7878 287 6360 3847 358 3107 2397 112 1094 2613 2705 4800 2985 9335 3412 3460 8596 4348 481 5617 2553 5648 284 6074 9484 5395 4286 2779 9407 6749 4276 2412 9099 9092 1729 2310 8124 4283 5110 2069 5504 6294 3441 3028 1376 8081 3712 4611 2318 6582 4166 6...
output:
308425632 281930664 421890658 52314367 394640692 324551164 8569803 380357591 44862713 186186675 283044388 485547282 414181010 18665219 356066909 105580995 107275969 156718441 110829727 84308858 495104234 480684438 294255662 457907123 393646648 431191656 20517329 29121182 259299589 31680850 91597604 ...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 39ms
memory: 15320kb
input:
100000 100000 3855 7345 5685 4096 685 7514 4991 98 3898 5786 5501 8643 9055 3471 2747 137 7108 8697 2909 3702 9648 4358 3548 1951 7493 1831 295 9472 9251 8879 618 5002 3636 4141 6394 4300 8724 594 80 3941 7238 5656 2333 8898 1513 9121 781 1704 2739 369 1130 9441 7866 2525 7533 5796 4730 6966 5988 86...
output:
2090767 6691232 63507273 29832155 478335606 2347523 7430493 940224 4874583 578261 1648141 450420770 3569725 11113813 6293860 2491083 1500248 475927 916374 1145855 9296595 9870533 796917 4669175 266523773 159256018 4297981 7002586 3531165 47388718 5299005 3262967 16145647 7322405 236113272 8662463 70...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 42ms
memory: 15300kb
input:
100000 100000 3444 5744 551 967 5919 1644 3318 8012 459 1619 4101 1872 3759 2337 7254 4375 6396 1293 8242 9865 4108 8241 599 9388 5345 4229 8446 5702 4685 4669 4750 7314 1836 4195 1564 5799 7394 1464 7942 1610 4424 4533 5287 1330 4310 1140 9549 8604 5048 6370 1986 3860 4137 3940 5551 298 9892 5658 8...
output:
50856311 1000246 19866630 1444539 439092138 26661714 442865978 590326 292178869 427072552 215168015 272669997 3155910 303535741 14439129 10289555 7514 464175906 26376 7397985 444050 5669313 82880904 1793281 475725971 6590087 432129208 325002255 36525899 81101662 71113061 3212995 232344331 172211957 ...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 44ms
memory: 13964kb
input:
100000 100000 8579 9098 1782 7994 284 1744 1132 8578 6909 1377 6938 194 4084 3680 9687 1827 1518 8448 3468 8814 1502 6423 847 1228 5273 6724 3067 128 3353 2196 9922 6122 921 4266 8879 5064 4098 3755 9325 803 3719 1456 7421 1168 1422 1598 8805 6872 6166 3177 765 2939 2398 7261 3120 3758 6917 9024 678...
output:
489534180 9002723 461272 11517029 3356 739786 466442529 4158137 39023936 182544214 409289842 389017 294443398 3591338 14245983 153302942 225684581 143605 780296 93336106 10623066 3291448 499765848 27132198 55276 478469482 43938 18204292 97412864 33714455 130429510 30512711 32121530 236507674 189418 ...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 40ms
memory: 13180kb
input:
100000 100000 6727 4070 2004 7056 2316 982 6809 422 3653 2454 6250 5657 3353 6867 181 5995 1869 6443 5370 9738 5802 6739 7993 3577 8161 3480 2589 9200 6632 6926 5945 1124 3247 2815 5146 2393 9154 5057 8967 9079 2879 961 9991 2812 2471 1986 6616 1201 2726 2840 2254 753 4596 7489 8450 8151 4117 3232 9...
output:
5234 474302 13363 154936833 77333 208865812 150256432 18907178 308424052 2813567 100169 5947638 695485 16595626 50960 79743342 30253 135929489 37388 469580043 10033009 79227640 15611 56140077 1965501 8877607 213313 64268155 57113992 799645 1912883 6878072 99257 6390512 5059604 46124508 411371922 953...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 31ms
memory: 12920kb
input:
100000 100000 5179 6667 9351 2278 1290 437 8982 2483 5077 1303 7 1548 7405 1687 3215 4207 2445 1604 1147 8637 4333 9835 5175 9346 267 6787 6457 8641 3692 6132 673 2976 1512 8895 3586 9092 4812 4316 9061 1884 475 6917 455 8387 4086 4925 3997 1105 9029 4344 6006 2029 501 5282 8844 3889 5989 9716 5159 ...
output:
126212 37889564 961139 3159564 2369680 13612008 452310892 14024759 490336557 9875714 10065501 63766 72553104 9814881 16486 14692605 3438278 78037824 10480789 4289187 121885741 193156801 4237573 266726 455870337 964357 28796 59405386 275096 53304423 372648182 1417388 4412799 10941 178276 2037517 6657...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 44ms
memory: 13196kb
input:
100000 100000 1287 5532 4603 3660 3811 890 1096 98 2862 9716 979 5961 9089 2237 9245 6636 5935 2707 7769 3942 3168 1250 4442 159 5653 8248 5399 466 2308 5827 5747 9352 2424 8007 9989 9072 6433 9754 5531 4552 2014 7339 8639 4003 6760 4551 1678 6721 4222 5185 8189 4541 9110 7051 1031 4576 3784 3482 19...
output:
225809161 558714 498524247 121783442 195030159 121037668 88883164 1305655 4014629 2306044 5863 123888828 36958 6906775 189101 4311201 3540126 219431 170559199 76961610 34630 4728299 3512 14476 299795 5223063 284843847 105518799 2399072 154066 3951 6566041 24285558 4083191 195016565 293086945 1248277...
result:
ok 100000 lines
Test #27:
score: 0
Accepted
time: 44ms
memory: 14036kb
input:
100000 100000 632 6205 3113 2561 4309 5539 1270 3378 8020 5732 9763 1467 4263 8305 2554 4087 5678 8558 2065 8296 6152 7371 5263 3092 6883 4225 4309 6812 8477 4275 9659 1171 3617 1989 2647 8806 4215 6258 1456 4836 8468 4731 4994 7609 2801 5588 5646 2513 9919 7181 9564 7802 973 6017 3629 3332 4864 825...
output:
22087 8412440 7179743 620786 221821 473590457 138940 2075681 479386324 494786569 489101711 75816 3570 42557 114941828 50173 16740020 142706 274419 5566457 117183 942084 12919407 26560886 14501 87756 14542 3247613 442050680 885 45812 14012 436388434 307181 497907994 2782484 45009 3997081 119745 52925...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 31ms
memory: 12680kb
input:
99999 100000 1444 3539 6930 1660 4454 572 5331 8008 5191 1377 4186 5742 5684 5296 2500 3939 450 3089 6663 4446 6375 2264 8441 4399 1073 9675 9837 5038 6654 2493 1433 2840 5093 9670 87 978 1633 9503 6709 7779 7715 6327 2055 6023 7756 882 8236 6198 2906 936 934 6510 6008 2637 2299 6045 1256 1637 433 6...
output:
84843 31596108 255852 288949 2545 38528 11915903 725491 135357624 108657 957324 712095 157210 229630427 116301 100916 90793 4770811 24505981 1149379 81634733 5558071 25477814 6616 196540 73365133 3296794 83205 23294013 20195511 408885382 19156 23935697 490098 1426 9881001 12153 121932 26246449 57556...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 38ms
memory: 12716kb
input:
99932 100000 6813 3036 1267 1167 3452 7872 9178 6099 6965 1123 6953 431 769 2212 2030 5139 3238 7729 5204 9632 6947 9886 44 4196 612 6795 8517 8476 4393 9050 7142 4759 639 9708 6793 6742 8242 7715 732 6040 3314 3080 2335 261 6281 1536 4370 504 6872 3919 7421 355 9483 9285 6436 1376 7743 4302 4339 32...
output:
68724643 7216713 142406304 6660669 358319781 159853 121034 2534513 24213314 37404 51462832 23290 112977 95668 14627991 26497531 394298 78287920 12614 4911833 239008 5980957 32752 42686 43004224 31805109 575235 206949 80420 291240943 13450621 15176 5433271 17996 6383 1530582 8536206 261027 393376 446...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 39ms
memory: 12712kb
input:
99999 100000 7440 9633 8827 4895 5672 3070 5881 6698 7883 7683 9717 3478 4876 437 6929 820 8193 9320 9017 8192 6429 1193 4634 8314 2325 3600 4679 704 9610 9672 5534 8276 1712 7871 813 6842 9326 3325 1315 8782 5974 5751 5784 105 5392 5020 4312 6676 6924 2532 901 8282 1246 6802 7285 3166 1436 7990 759...
output:
56273904 146325991 27636 6127581 500079 1671205 1322 2553409 27207459 329726699 66644185 20655 2373601 234639 2571691 6405552 30155 4025 7129902 196216 25680886 29207 75162811 12503867 273666 4130152 841730 653105 75412 217214560 112068 3154577 193111 3983623 148589996 28333494 32611855 585761 92046...
result:
ok 100000 lines
Test #31:
score: 0
Accepted
time: 36ms
memory: 15348kb
input:
100000 100000 4062 4361 259 808 2158 4583 9966 3261 1204 8591 6923 7230 2444 6693 700 2688 8570 7018 6828 5058 1372 9134 5785 1744 8492 9013 7031 874 6395 2783 4279 98 9046 5562 8307 7912 5472 3915 8266 4067 8715 2687 3208 8344 1830 3567 6771 2869 1294 1769 1002 2758 6243 3180 6166 8265 1910 2526 82...
output:
63598350 432580481 446041993 117531176 146851735 263503610 308149489 381279876 97518859 311648585 451609830 368156573 42004739 196832021 253064795 97503114 118570613 341822808 359478549 323994689 380312219 75595312 437046945 170299289 244577412 171966311 228926188 478808436 286699186 289676221 15772...
result:
ok 100000 lines