QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#700917 | #66. Two Dishes | TheZone | 100 ✓ | 1551ms | 191496kb | C++23 | 3.4kb | 2024-11-02 13:32:23 | 2024-11-02 13:32:24 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, LL> PII;
typedef set<PII>::iterator SIT;
const int N = 1e6 + 5;
int n, m, A[N], P[N], x[N], y[N];
int B[N], Q[N];
LL S[N], T[N], sa[N], sb[N];
LL res, ans;
set<PII> s;
vector<PII> e[N];
void inline add(int x, int y, int c) {
if (x < 0 || x > n || y < 0 || y > m) return;
e[x].pb(mp(y, c));
}
void inline chkMax(LL &x, LL y) {
if (y > x) x = y;
}
void inline insert(int x, int y) {
SIT it = s.lower_bound(mp(x, 0));
PII o = mp(x, y);
if (it -> fi == x) {
o = *it;
s.erase(it);
o.se += y;
}
if (o.se == 0) return;
if (o.se < 0) {
LL t = -o.se;
while (1) {
it = s.lower_bound(mp(x, 0));
if (it == s.end()) break;
LL d = min(t, it -> se);
PII b = *it; s.erase(it);
b.se -= d; t -= d;
if (b.se > 0) s.insert(b);
if (t == 0) break;
}
} else {
s.insert(o);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%lld%d", A + i, S + i, P + i), sa[i] = sa[i - 1] + A[i];
for (int i = 1; i <= m; i++)
scanf("%d%lld%d", B + i, T + i, Q + i), sb[i] = sb[i - 1] + B[i];
for (int i = 1; i <= n; i++) {
int l = 0, r = m;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (sb[mid] + sa[i] <= S[i]) l = mid;
else r = mid - 1;
}
if (sb[r] + sa[i] <= S[i]) y[i] = r;
else y[i] = -1;
}
for (int i = 1; i <= m; i++) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (sb[i] + sa[mid] <= T[i]) l = mid;
else r = mid - 1;
}
if (sb[i] + sa[r] <= T[i]) x[i] = r;
else x[i] = -1;
}
for (int i = 1; i <= n; i++) {
if (y[i] >= 0) {
res += P[i];
add(i - 1, y[i] + 1, -P[i]);
}
}
for (int i = 1; i <= m; i++) {
if (x[i] >= 0) add(x[i], i, Q[i]);
}
for (int i = 0; i <= n; i++) {
sort(e[i].begin(), e[i].end(), greater<PII>() );
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < e[i].size(); j++) {
PII v = e[i][j];
insert(v.fi, v.se);
}
}
for (SIT u = s.begin(); u != s.end(); u++) res += u -> se;
for (int i = 0; i < e[n].size(); i++) res += e[n][i].se;
printf("%lld\n", res);
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 206ms
memory: 64568kb
input:
200000 200000 278709225 90000000000000 119140441 16903947 90000000000000 50995483 544180428 90000000000000 38297640 196030639 90000000000000 34905015 488761573 90000000000000 161103211 679613271 90000000000000 17751356 966475096 90000000000000 46222110 551036816 90000000000000 155177091 587245324 90...
output:
107963696072360
result:
ok single line: '107963696072360'
Test #2:
score: 5
Accepted
time: 108ms
memory: 44272kb
input:
193493 200000 925058333 110000000000000 902655295 969346274 110000000000000 897063383 274276678 110000000000000 998492209 155091206 110000000000000 952470530 427199270 110000000000000 896313513 639254566 110000000000000 996267081 167829821 110000000000000 801226486 914764704 110000000000000 96254537...
output:
184676136004816
result:
ok single line: '184676136004816'
Test #3:
score: 5
Accepted
time: 88ms
memory: 34796kb
input:
200000 200000 78709225 90000000000000 119140441 16903947 90000000000000 50995483 144180428 90000000000000 38297640 196030639 90000000000000 34905015 88761573 90000000000000 161103211 79613271 90000000000000 17751356 166475096 90000000000000 46222110 151036816 90000000000000 155177091 187245324 90000...
output:
140049205271847
result:
ok single line: '140049205271847'
Test #4:
score: 5
Accepted
time: 153ms
memory: 54096kb
input:
193493 200000 982738968 110000000000000 102655295 803748915 110000000000000 97063383 901631098 110000000000000 198492209 970118580 110000000000000 152470530 873571720 110000000000000 96313513 957118364 110000000000000 196267081 992666794 110000000000000 1226486 857385432 110000000000000 162545375 95...
output:
73306782762089
result:
ok single line: '73306782762089'
Test #5:
score: 5
Accepted
time: 0ms
memory: 22392kb
input:
1 1 501529716 500000000 662608471 412844516 500000000 397784761
output:
397784761
result:
ok single line: '397784761'
Test #6:
score: 5
Accepted
time: 117ms
memory: 50768kb
input:
193648 189234 409900959 120000000000000 152145896 761018965 120000000000000 785003327 61396280 120000000000000 238026895 989062668 120000000000000 524504013 855153803 120000000000000 315249534 872338642 120000000000000 358968223 409250223 120000000000000 871827818 321869121 120000000000000 719848927...
output:
120307438151821
result:
ok single line: '120307438151821'
Test #7:
score: 5
Accepted
time: 40ms
memory: 33624kb
input:
1 200000 642993987 90000000000000 46073412 302380913 90000000000000 344682541 939348219 90000000000000 137977286 948161029 90000000000000 72596149 246590337 90000000000000 344586083 113422629 90000000000000 814150276 648901813 90000000000000 921420921 898034405 90000000000000 148425791 535266847 900...
output:
89969298579857
result:
ok single line: '89969298579857'
Test #8:
score: 5
Accepted
time: 44ms
memory: 25972kb
input:
200000 1 321566392 110000000000000 863747384 596772228 110000000000000 296502218 325454648 110000000000000 70164619 275895183 110000000000000 187787467 377086551 110000000000000 217279488 865517362 110000000000000 47298654 840579552 110000000000000 468914321 854986985 110000000000000 431496950 91797...
output:
99908911815069
result:
ok single line: '99908911815069'
Test #9:
score: 5
Accepted
time: 93ms
memory: 33112kb
input:
200000 200000 345286913 2000000000000000 376318746 219589528 2000000000000000 263352205 791814494 2000000000000000 77274228 580955195 2000000000000000 782313709 645431758 2000000000000000 781742022 20206380 2000000000000000 387136126 510328362 2000000000000000 953287814 819498100 2000000000000000 29...
output:
200001406161703
result:
ok single line: '200001406161703'
Test #10:
score: 5
Accepted
time: 152ms
memory: 51848kb
input:
200000 200000 1 200000 853767530 1 200000 755242887 1 200000 215803462 1 200000 101732824 1 200000 376828586 1 200000 690016218 1 200000 534818238 1 200000 648068478 1 200000 903957311 1 200000 809197499 1 200000 650941838 1 200000 867329819 1 200000 433581785 1 200000 586449792 1 200000 824550754 1...
output:
100000287734558
result:
ok single line: '100000287734558'
Test #11:
score: 5
Accepted
time: 61ms
memory: 38400kb
input:
200000 200000 3 6000000 928325552 1 6000000 743507163 5 6000000 106567808 5 6000000 494151314 4 6000000 291532803 2 6000000 163124810 3 6000000 760825535 4 6000000 272587154 4 6000000 352420321 4 6000000 905539622 5 6000000 620823619 4 6000000 604273601 1 6000000 770891408 5 6000000 999883946 4 6000...
output:
200153672337270
result:
ok single line: '200153672337270'
Subtask #2:
score: 3
Accepted
Test #12:
score: 3
Accepted
time: 0ms
memory: 22372kb
input:
12 12 884953730 1099691010 1 4015595 1477095709 1 726912949 2466785273 1 519508315 3990478241 1 708508942 5296800362 1 12364496 5320678730 1 286349693 6142173547 1 699837926 7037986902 1 934065390 8380990679 1 697606387 9347495140 1 875580140 10957110966 1 68179052 11776535162 1 344720591 838815847 ...
output:
12
result:
ok single line: '12'
Test #13:
score: 3
Accepted
time: 0ms
memory: 22280kb
input:
12 12 551691302 324632420 1 800582045 1348372403 1 14063803 14733602 1 52897269 256428825 1 153641504 1321745671 1 567834643 1337247037 1 453508034 1270193155 1 853479486 1945292068 1 949940012 170066870 1 931639209 404493902 1 527379143 3215826828 1 577323364 5341297473 1 454806733 35892194 1 54812...
output:
0
result:
ok single line: '0'
Test #14:
score: 3
Accepted
time: 0ms
memory: 22288kb
input:
12 12 286992568 900884294230763 1 522764708 179131135421401 1 858066681 221639310388039 1 411939222 616689146281519 1 278314510 411477603071162 1 736125071 481740908324652 1 314440633 586310260559054 1 992793856 538907614540791 1 734353326 623035949795417 1 240422976 537878602920600 1 225920052 3662...
output:
24
result:
ok single line: '24'
Test #15:
score: 3
Accepted
time: 0ms
memory: 22348kb
input:
12 12 560229147 876116411 1 762334640 1757956471 1 867292782 2271331496 1 513185346 2927972170 1 675220997 3573453786 1 452421504 4067817691 1 886937109 4734080537 1 711237939 5762262791 1 896169516 6500399725 1 182782794 6807543233 1 835794911 7462054577 1 100130164 7844981638 1 449688435 589791881...
output:
14
result:
ok single line: '14'
Test #16:
score: 3
Accepted
time: 0ms
memory: 22232kb
input:
12 12 958635898 253267141 1 157893686 685493591728951 1 976682032 720188590843821 1 790021767 2653778664 1 534783017 484912905 1 706987897 308457305655477 1 510148270 795920657967813 1 216566011 4754666709 1 288661613 728628635771894 1 856715472 883841683245416 1 81126924 4203988529 1 420966670 4746...
output:
19
result:
ok single line: '19'
Test #17:
score: 3
Accepted
time: 4ms
memory: 22364kb
input:
1 1 746491541 766814901 1 626145740 1256744672 1
output:
1
result:
ok single line: '1'
Test #18:
score: 3
Accepted
time: 4ms
memory: 22372kb
input:
12 12 450674304 2759730567 1 915813217 5865385994 1 429462295 1868112012 1 552626810 6878616256 1 521822262 2545854184 1 647591556 8576857974 1 530796658 132975736 1 97727387 8812772481 1 676240804 9699971390 1 193591298 6171207510 1 672069644 11153585817 1 218579173 6952631413 1 22151020 4121542856...
output:
14
result:
ok single line: '14'
Test #19:
score: 3
Accepted
time: 0ms
memory: 22424kb
input:
9 12 414814218 278771326 1 142790158 568604393 1 155567225 14012701 1 627555390 1224920860 1 677068511 5243031298 1 580933994 8598159379 1 819258172 1432469030 1 340548310 999347990 1 432162069 4373255579 1 99824657 11080715 1 756309567 9502204999 1 929699364 2343419815 1 376204577 6097684636 1 3995...
output:
6
result:
ok single line: '6'
Test #20:
score: 3
Accepted
time: 0ms
memory: 22368kb
input:
12 10 137685809 4249908213 1 888460570 6162167606 1 255401748 10310161799 1 574333708 5886505525 1 397332471 11008944494 1 68658609 10903747442 1 197555281 11638006542 1 944017921 12085863407 1 517938137 11772193793 1 775951900 14155878649 1 369629841 10039210915 1 856625908 11780413129 1 792090374 ...
output:
22
result:
ok single line: '22'
Test #21:
score: 3
Accepted
time: 0ms
memory: 22364kb
input:
12 12 1 10 1 1 1 1 1 13 1 1 7 1 1 11 1 1 7 1 1 18 1 1 17 1 1 21 1 1 19 1 1 18 1 1 18 1 1 1 1 1 13 1 1 6 1 1 8 1 1 15 1 1 3 1 1 14 1 1 16 1 1 15 1 1 10 1 1 21 1 1 15 1
output:
17
result:
ok single line: '17'
Test #22:
score: 3
Accepted
time: 0ms
memory: 22368kb
input:
12 12 1 16 1 2 28 1 2 14 1 3 25 1 3 39 1 2 14 1 3 21 1 1 32 1 1 43 1 1 23 1 3 24 1 3 30 1 2 37 1 2 9 1 3 29 1 2 35 1 1 16 1 2 2 1 2 31 1 1 22 1 2 35 1 1 20 1 3 21 1 1 38 1
output:
15
result:
ok single line: '15'
Test #23:
score: 3
Accepted
time: 0ms
memory: 22364kb
input:
12 12 89799642 49692259 1 229399564 811740996 1 135485930 841109682 1 431810470 9513334855 1 294721716 4487512793 1 324331816 5359589182 1 478365662 3315887541 1 47534872 4309614247 1 205679728 5535047461 1 791160453 1200926698 1 614191623 5057551186 1 764668366 10713756692 1 685693506 2750639180 1 ...
output:
15
result:
ok single line: '15'
Test #24:
score: 3
Accepted
time: 0ms
memory: 22372kb
input:
5 12 776828142 1397545734 1 189506344 2160364868 1 58596121 5966553855 1 272883209 1139924761 1 45729954 5446434658 1 927047364 68907031 1 68493905 1982484482 1 512459772 1263184765 1 774136355 6191784333 1 396934216 5374853900 1 667853683 6656165826 1 580790148 8440557419 1 298336860 6088273637 1 7...
output:
10
result:
ok single line: '10'
Test #25:
score: 3
Accepted
time: 0ms
memory: 22292kb
input:
12 3 538372153 2607291479 1 17670010 360747035 1 715398730 881558330 1 212550828 3547752331 1 448734103 3475078328 1 243463405 4013385464 1 822213572 2805893143 1 109881706 6004746417 1 701427369 5274623662 1 125209451 5783604167 1 589280031 5401871987 1 351006393 5098345877 1 570369185 4699950172 1...
output:
10
result:
ok single line: '10'
Test #26:
score: 3
Accepted
time: 3ms
memory: 22356kb
input:
8 12 466421672 322419685 1 829839951 10803101238 1 43196804 2794274548 1 743316313 5015041198 1 798441550 6185579270 1 767420588 11240247616 1 39283192 5491197636 1 184273471 368244362 1 558308306 1222463139 1 893919920 1809209594 1 4053601 2761904900 1 813073191 5927619356 1 645542021 2085805592 1 ...
output:
12
result:
ok single line: '12'
Test #27:
score: 3
Accepted
time: 5ms
memory: 22284kb
input:
12 4 979929308 3107436230 1 428664578 3323216326 1 914625879 2756659832 1 404226469 6714121618 1 581278541 6543352379 1 362841137 7530929877 1 32024229 4571060808 1 435623827 7843360378 1 920715456 7745344797 1 205825433 7953967897 1 455568658 8391536383 1 946687914 10252503424 1 993197404 974833302...
output:
14
result:
ok single line: '14'
Subtask #3:
score: 7
Accepted
Dependency #2:
100%
Accepted
Test #28:
score: 7
Accepted
time: 5ms
memory: 22560kb
input:
1999 2000 515391161 763795702 1 611274809 1261562553 1 241579177 1638313844 1 794330740 2675506869 1 10171859 2788754450 1 421070901 3085449583 1 191803444 3359041514 1 462515964 3413105535 1 942558211 4921260476 1 789307312 5230580771 1 749632607 6428848493 1 168283015 6307563953 1 741578406 725117...
output:
3006
result:
ok single line: '3006'
Test #29:
score: 7
Accepted
time: 4ms
memory: 22456kb
input:
2000 2000 977045956 471656263488432 1 164570698 544516146950584 1 184755663 49641816362108 1 365443392 950619563758866 1 688612912 611528357573017 1 603003602 167178849837844 1 845988325 45666940 1 69841518 389869119824197 1 124418966 599032577331771 1 495851703 1795343372 1 221534905 8803126 1 9258...
output:
3010
result:
ok single line: '3010'
Test #30:
score: 7
Accepted
time: 5ms
memory: 22504kb
input:
2000 2000 888945549 6597059176 1 428603708 95966025326 1 383232136 897851857457 1 695719431 574325043037 1 225206990 575657684068 1 308184262 923436400625 1 628525462 1132053696837 1 842180289 75628606376 1 95193624 84640375432 1 254757702 571142915018 1 542955837 119322101239 1 252366421 1158754289...
output:
2145
result:
ok single line: '2145'
Test #31:
score: 7
Accepted
time: 5ms
memory: 24540kb
input:
2000 1853 670674530 50926657892 1 495195316 419655531680 1 490372978 512122889 1 797821088 1385196699 1 23160229 328741921 1 70776335 1789689959 1 762368375 108629421906 1 698037053 943239738989 1 455709554 1931258015 1 47888549 508584001806 1 845792326 785954126530 1 820951574 2458901941 1 54455538...
output:
1088
result:
ok single line: '1088'
Test #32:
score: 7
Accepted
time: 5ms
memory: 22444kb
input:
1924 2000 756701266 894992938839 1 817177749 1855254325724 1 572689391 679942344598 1 99996538 585203661251 1 642038567 749454653215 1 617775243 730582259743 1 853124406 694062360970 1 399454416 514938074685 1 44070185 854472820813 1 210538665 941352354205 1 997350872 626596196929 1 988218611 550753...
output:
3218
result:
ok single line: '3218'
Test #33:
score: 7
Accepted
time: 5ms
memory: 22576kb
input:
2000 2000 1 442 1 1 505 1 1 1053 1 1 549 1 1 1300 1 1 631 1 1 1367 1 1 1400 1 1 936 1 1 941 1 1 1558 1 1 1126 1 1 1271 1 1 377 1 1 1316 1 1 1125 1 1 1028 1 1 1042 1 1 644 1 1 892 1 1 1762 1 1 1650 1 1 878 1 1 337 1 1 2021 1 1 149 1 1 167 1 1 607 1 1 325 1 1 805 1 1 433 1 1 339 1 1 1342 1 1 271 1 1 1...
output:
2090
result:
ok single line: '2090'
Test #34:
score: 7
Accepted
time: 2ms
memory: 22584kb
input:
2000 2000 1 4860 1 4 6954 1 2 3697 1 3 2870 1 1 4275 1 3 351 1 1 3694 1 3 220 1 1 3285 1 4 356 1 2 7431 1 3 341 1 3 1502 1 2 4086 1 3 1644 1 1 3112 1 5 2329 1 4 2312 1 4 1914 1 3 5974 1 1 485 1 4 1502 1 3 3334 1 3 5229 1 3 4352 1 1 4328 1 5 2116 1 4 1841 1 1 4584 1 1 3830 1 1 439 1 1 3602 1 2 2542 1...
output:
2113
result:
ok single line: '2113'
Subtask #4:
score: 39
Accepted
Dependency #3:
100%
Accepted
Test #35:
score: 39
Accepted
time: 77ms
memory: 42948kb
input:
200000 200000 997698065 1023821866 1 269692358 1389349329 1 607170799 1944366847 1 516351186 2485184379 1 935984256 3362372522 1 899165316 4310826413 1 231654824 4495598131 1 951113023 5443901040 1 844276634 6326886390 1 397634275 6655091165 1 272944023 7018964189 1 356674362 7343600279 1 331036300 ...
output:
300187
result:
ok single line: '300187'
Test #36:
score: 39
Accepted
time: 129ms
memory: 45092kb
input:
200000 199999 864888449 321413767 1 473961621 170106790 1 190522959 951283046552705 1 820646665 186049068 1 22301217 650696254682916 1 9492513 491822481857728 1 860062372 275051916431383 1 37064228 376546475720216 1 902791815 498850717553358 1 391795076 219084122442958 1 731578247 5280185010 1 19718...
output:
300064
result:
ok single line: '300064'
Test #37:
score: 39
Accepted
time: 81ms
memory: 49528kb
input:
199999 199999 458162947 611595642 1 175643977 1338679925 1 727270078 2680353136 1 122110004 3545231242 1 24786112 3686263336 1 260954842 4113010463 1 378646915 4703058111 1 422692851 5845217248 1 377845733 6346336935 1 473430752 6963508264 1 468331006 7771729732 1 663764144 8849508308 1 327593225 95...
output:
299919
result:
ok single line: '299919'
Test #38:
score: 39
Accepted
time: 132ms
memory: 62912kb
input:
200000 200000 579688376 382937363 1 471315639 899565849 1 73440809 555439640 1 909550586 113290738631549 1 860952046 358362661 1 759672613 375691126576003 1 718627966 1892055940 1 499195004 112270615930314 1 770008372 1388465102 1 236201261 1682259346 1 100210626 4041567770 1 445253931 1320635327 1 ...
output:
300136
result:
ok single line: '300136'
Test #39:
score: 39
Accepted
time: 103ms
memory: 39000kb
input:
200000 200000 438384814 46599373446280 1 242632531 277458945797670 1 11446033 330799469008789 1 709180318 83267994913452 1 31970981 276704195932692 1 447769525 94582759778718 1 72132404 290312525868845 1 99284585 81622772318080 1 628120785 297071546680934 1 93794542 295899099544911 1 611381209 87429...
output:
300588
result:
ok single line: '300588'
Test #40:
score: 39
Accepted
time: 72ms
memory: 38120kb
input:
200000 200000 587199200 2000000000000000 1 532201403 2000000000000000 1 8872164 2000000000000000 1 443390545 2000000000000000 1 467817920 2000000000000000 1 174720507 2000000000000000 1 54297826 2000000000000000 1 425639335 2000000000000000 1 465114681 2000000000000000 1 95069547 2000000000000000 1 ...
output:
400000
result:
ok single line: '400000'
Test #41:
score: 39
Accepted
time: 207ms
memory: 53792kb
input:
200000 200000 334632844 16274135177545 1 386622774 50825326034155 1 528258658 99522299039877 1 766408591 61303770451401 1 570739595 171555294489520 1 667500508 93249094472292 1 179586402 30463513919334 1 281562532 16296376914732 1 567999721 29972540915638 1 546396559 85129477176116 1 180410887 27877...
output:
201428
result:
ok single line: '201428'
Test #42:
score: 39
Accepted
time: 58ms
memory: 33328kb
input:
1 200000 30737772 16040363054787 1 494146605 507694953 1 163611368 1407558367 1 683331429 2007373418 1 340542838 1703085043 1 334270729 2036082570 1 991956413 3036656159 1 2310435 3458899995 1 580894798 3744096166 1 741415473 4334119063 1 619691605 4953269049 1 696651907 6642477271 1 322946088 65783...
output:
200000
result:
ok single line: '200000'
Test #43:
score: 39
Accepted
time: 34ms
memory: 38812kb
input:
200000 1 799822153 964760988 1 782914217 2578125684 1 55647649 2592763578 1 15876266 2021821485 1 162716476 2785976431 1 494720504 3065835685 1 510051845 3018669633 1 296011315 4078601297 1 376532888 4472065797 1 168832432 4615664799 1 348315196 4966906111 1 305981374 4333429946 1 382367095 56138158...
output:
200000
result:
ok single line: '200000'
Test #44:
score: 39
Accepted
time: 136ms
memory: 44280kb
input:
195334 200000 843788521 654129118 1 960847714 1587160327 1 9430464 6523301011940 1 258842065 44989057948944 1 2226930 27275934362292 1 589574674 84670108883770 1 125533909 29562223400269 1 520539817 17803049549481 1 417673920 81802292249664 1 792900148 1618317625 1 297414109 48789244501832 1 1152717...
output:
102490
result:
ok single line: '102490'
Test #45:
score: 39
Accepted
time: 180ms
memory: 52512kb
input:
200000 191356 925336928 87880463370406 1 923267791 83412632831090 1 129505888 62799307192343 1 930021102 73763309250581 1 146259111 56173403220375 1 785710560 50788653176448 1 887208389 82022243196678 1 864696811 56257468610049 1 257475306 73060572624940 1 914162993 54994621169238 1 620473425 614869...
output:
316088
result:
ok single line: '316088'
Test #46:
score: 39
Accepted
time: 193ms
memory: 54108kb
input:
200000 200000 1 110406 1 1 59975 1 1 10273 1 1 112698 1 1 3692 1 1 101653 1 1 188043 1 1 112899 1 1 91299 1 1 172752 1 1 73143 1 1 27778 1 1 143816 1 1 156891 1 1 175497 1 1 122312 1 1 70482 1 1 35635 1 1 123323 1 1 48765 1 1 130348 1 1 193361 1 1 24581 1 1 9 1 1 150953 1 1 186357 1 1 171174 1 1 997...
output:
201561
result:
ok single line: '201561'
Test #47:
score: 39
Accepted
time: 182ms
memory: 51688kb
input:
200000 200000 1 505013 1 2 498364 1 4 339881 1 2 121130 1 2 467399 1 1 487606 1 4 596447 1 4 364921 1 3 550540 1 4 299871 1 4 403863 1 4 919469 1 3 534862 1 5 385306 1 1 448036 1 4 10887 1 1 30645 1 3 453776 1 1 411223 1 2 145918 1 4 367602 1 3 266556 1 2 468652 1 2 231923 1 1 445193 1 4 354546 1 3 ...
output:
201501
result:
ok single line: '201501'
Subtask #5:
score: 11
Accepted
Dependency #4:
100%
Accepted
Test #48:
score: 11
Accepted
time: 98ms
memory: 42336kb
input:
200000 200000 298961082 99761086323151 129806250 363519903 99760889469672 313979789 990863132 99761447918630 902271296 391598048 99761319415609 152470327 540262746 99761610624631 651450226 666620136 99761373781623 353383972 712170125 99761468231150 467094922 406883722 99761198254106 783474893 697848...
output:
149953856090579
result:
ok single line: '149953856090579'
Test #49:
score: 11
Accepted
time: 142ms
memory: 60988kb
input:
200000 200000 944874833 946150044455271 727294723 417567478 748491508 459351221 336356835 828571586103954 458589605 833384570 1619001793 697090447 765243167 3106816218 66633140 238656010 707018528641705 950403061 423619866 1278554966 323231564 1760010 3738784657 211694719 526864286 841679911993449 3...
output:
149597616748329
result:
ok single line: '149597616748329'
Test #50:
score: 11
Accepted
time: 208ms
memory: 59328kb
input:
200000 200000 79122220 99746040374574 1 850909973 99746584099672 1 498975192 99746782287572 1 87960186 99746559294326 1 845841575 99746747474090 1 196688005 99746458511062 1 967089520 99747262416653 1 86349390 99747209213280 1 443735765 99747229126416 1 904722601 99747861885713 1 307740570 997476925...
output:
1000199999
result:
ok single line: '1000199999'
Test #51:
score: 11
Accepted
time: 109ms
memory: 47980kb
input:
200000 200000 214756303 99853927379101 1367 32288894 99853183214635 2482 525933331 99853536099138 1360 951805423 99854405206763 721 832749071 99854628701592 2497 802453831 99855247631989 2353 157869747 99854969067715 2435 599001295 99855114647840 1271 736231122 99855475770989 683 486925107 998555188...
output:
1000199999
result:
ok single line: '1000199999'
Test #52:
score: 11
Accepted
time: 4ms
memory: 22372kb
input:
1 1 972394581 1246249626 784434497 959741939 1942914328 731917398
output:
1516351895
result:
ok single line: '1516351895'
Test #53:
score: 11
Accepted
time: 263ms
memory: 55488kb
input:
200000 200000 717365271 29925592708320 308562580 630039019 529794789 625894349 418530142 60648991876010 411808089 656902465 66605091046374 489609961 110861088 2929935147601 833887701 646662239 62356552846442 645773506 118179280 19712043567294 902204536 853883235 76973979740553 579052677 334093544 70...
output:
100893398485842
result:
ok single line: '100893398485842'
Test #54:
score: 11
Accepted
time: 169ms
memory: 45992kb
input:
193628 200000 927534154 77454246516931 302894118 486905813 562354234 964686424 301650160 38336964063397 927092701 811250388 86749766892777 56981404 192051373 23228327574473 253514699 517856587 92758394725578 988501656 67952327 56930215241463 14300877 539441344 1407516441 719572225 151306106 10206491...
output:
51288994128593
result:
ok single line: '51288994128593'
Test #55:
score: 11
Accepted
time: 193ms
memory: 55640kb
input:
200000 189534 750514588 134734557272549 211180370 877350718 72776912291896 259060775 127971537 93324271792485 621204726 229471367 62824197480932 323051827 87827098 140669726952077 957855133 157568818 63621149862636 35432817 733509562 154756366309607 674953835 101495140 59560197369762 32585598 738379...
output:
158056872743750
result:
ok single line: '158056872743750'
Test #56:
score: 11
Accepted
time: 247ms
memory: 50208kb
input:
200000 200000 1 132162 114080239 1 156879 525699517 1 75714 685935769 1 199770 85640256 1 91927 683084722 1 10385 295290959 1 68715 257667384 1 61359 263520230 1 48377 760825038 1 109070 746783604 1 89594 82670283 1 184278 375645260 1 169160 566085489 1 142849 806111546 1 200015 30564949 1 14067 369...
output:
100949563486806
result:
ok single line: '100949563486806'
Subtask #6:
score: 9
Accepted
Dependency #5:
100%
Accepted
Test #57:
score: 9
Accepted
time: 507ms
memory: 121216kb
input:
1000000 1000000 245790387 499397236501752 783985746 296284224 499397297805808 886109037 368089759 499397406786446 87383438 81723212 499397101634699 150908236 527628951 499396983654314 665942850 931868062 499397289563114 323373722 64671922 499396967304215 697407570 984788017 499396931371976 934282385...
output:
750178018675788
result:
ok single line: '750178018675788'
Test #58:
score: 9
Accepted
time: 812ms
memory: 175664kb
input:
1000000 1000000 993024457 831817339 246075049 108477765 821393486525128 795361323 465911276 949557144184681 191106236 69953800 932950073319595 262330738 723189403 611874141920373 665353071 659071024 667076690 90226002 668896933 649269788220681 773344095 831403976 699473596306998 770391908 271630523 ...
output:
749540199817851
result:
ok single line: '749540199817851'
Test #59:
score: 9
Accepted
time: 1224ms
memory: 191336kb
input:
1000000 1000000 719037809 500708402042158 1 66683481 500707726230726 1 204972353 500707691288967 1 310481632 500707417732187 1 395476241 500707640735207 1 72478712 500707462227929 1 563807173 500707575893194 1 653976464 500707985488501 1 625565205 500707868010573 1 112954134 500706943316541 1 388240...
output:
1000999999
result:
ok single line: '1000999999'
Test #60:
score: 9
Accepted
time: 546ms
memory: 129008kb
input:
1000000 1000000 688875491 499960328350507 382 932433934 499961092415658 429 833003565 499961884681851 104 55719061 499961021546288 336 646386122 499961611783706 424 280728089 499961350169068 477 341324166 499961037702454 155 431106913 499961196889471 115 264299866 499960685536187 297 620511003 49996...
output:
1000999999
result:
ok single line: '1000999999'
Test #61:
score: 9
Accepted
time: 1551ms
memory: 139920kb
input:
1000000 1000000 30768332 197575477068518 277598106 516710967 545587678896187 600106326 215083384 140048927814854 943607196 882229596 100833873459543 218010258 608157547 194472567386407 41056675 551405396 95645664763564 193062599 574244455 35824950674560 20930826 93507086 464061304589142 342953217 38...
output:
501791904267381
result:
ok single line: '501791904267381'
Test #62:
score: 9
Accepted
time: 885ms
memory: 107076kb
input:
934518 1000000 996565221 398131428678052 839860855 142111968 136016286495538 26110182 655529905 180045703043073 614142096 280000160 446164518633608 913682106 268931158 157465433380039 806742704 263906758 2340955438 974911771 949833096 23816203464985 80679994 286014515 184410360964700 217657122 37592...
output:
254376259023502
result:
ok single line: '254376259023502'
Test #63:
score: 9
Accepted
time: 1210ms
memory: 149532kb
input:
1000000 883248 883146129 449094758199823 698545970 91173925 361705745940050 91874133 129603845 838712483877822 406916135 640209620 846744904901006 419363195 455685184 292410892343279 476596229 656372704 427100526315466 3692065 687918730 389640954837743 803434479 978686873 780546058598738 120620287 2...
output:
782964237020590
result:
ok single line: '782964237020590'
Test #64:
score: 9
Accepted
time: 1425ms
memory: 137752kb
input:
1000000 1000000 3 1272690 590684434 4 503612 424507278 5 441340 294340782 5 1547172 499551424 4 1023720 797189962 5 3918494 121378046 2 774495 559332189 2 1196508 223151041 5 1379407 447892996 3 2514854 748950734 1 1919280 575741865 1 3395 848465921 2 1803987 414033904 4 1946403 967342620 4 2781741 ...
output:
502373630539657
result:
ok single line: '502373630539657'
Subtask #7:
score: 17
Accepted
Dependency #1:
100%
Accepted
Dependency #5:
100%
Accepted
Test #65:
score: 17
Accepted
time: 145ms
memory: 60328kb
input:
200000 200000 580334908 807216617 -444115777 632498256 1562870708 -403317872 820316400 3319637010 -706885497 821259216 4225595444 -590247019 853162668 5329885238 -519687773 7380790 5810916565 -449649957 926652658 7252255001 -696197765 392575810 7810762663 -28955078 968347369 9471731839 -209377056 62...
output:
-50120573402371
result:
ok single line: '-50120573402371'
Test #66:
score: 17
Accepted
time: 98ms
memory: 48576kb
input:
200000 200000 257497130 26049067 -467812377 405835060 400501780390623 -3353773 561469001 528255018350824 -255631407 278268250 226311293309100 -119132567 567410269 143063310136366 -127456196 424061057 1216664493 -520081162 37399348 970021648130172 -308622651 4203360 427861483825456 -603215684 3712245...
output:
-49939200178148
result:
ok single line: '-49939200178148'
Test #67:
score: 17
Accepted
time: 110ms
memory: 55576kb
input:
200000 200000 855641178 100096279421823 -1000000000 372252229 100095978888452 680 285187830 100095421572212 269 216593951 100095433305475 187 346667678 100095171158667 470 164647511 100095323540599 931 933541613 100095856483129 761 247317341 100095241900617 643 216116602 100095274815762 165 18329419...
output:
-166897385
result:
ok single line: '-166897385'
Test #68:
score: 17
Accepted
time: 206ms
memory: 64088kb
input:
200000 200000 930523876 100220583494363 -927 863722482 100221149336653 -397 847389572 100221549896885 -537 786672166 100221558808814 -860 435867293 100221926285150 -168 874014006 100222514467296 -406 537380763 100222688989848 -91 639126688 100222921858949 -928 935142940 100222836679477 -1352 4966014...
output:
-166672857
result:
ok single line: '-166672857'
Test #69:
score: 17
Accepted
time: 133ms
memory: 50276kb
input:
200000 200000 138591463 15703457487028 0 373586645 77531518093699 0 424398499 38136893217585 0 236902938 8885235852568 0 637798275 55292643066162 0 189810397 16195073815285 0 648982932 46262310416719 0 729656372 55572504861651 0 760735729 60012822128998 0 761442076 6785063209842 0 115215630 92987899...
output:
0
result:
ok single line: '0'
Test #70:
score: 17
Accepted
time: 4ms
memory: 22420kb
input:
1 1 468512468 748325173 705717094 459901058 830104491 -971967427
output:
705717094
result:
ok single line: '705717094'
Test #71:
score: 17
Accepted
time: 247ms
memory: 49012kb
input:
200000 200000 845376622 30828959862729 393370561 726124048 64829216214148 492723478 180555445 82608613197623 35029901 279045873 78296473066390 581033093 173634675 89178652396744 736910856 938368695 8915848929000 -239389872 259133077 26031824389483 759921145 34550648 92490028510696 418671419 98207279...
output:
40861684665895
result:
ok single line: '40861684665895'
Test #72:
score: 17
Accepted
time: 170ms
memory: 46256kb
input:
200000 192359 378414660 248996381 953702940 575107438 77482520600928 923587576 382419234 163850265002289 740741240 215628283 612847335 -716035814 274195100 85104842986326 -311366615 284775847 13297291647292 219169339 976091849 4893788 535302148 993263890 95976595789771 3948201 378223821 808217564199...
output:
31326658788976
result:
ok single line: '31326658788976'
Test #73:
score: 17
Accepted
time: 199ms
memory: 51960kb
input:
189354 200000 391735487 71873187481502 891092135 927649723 54172840029209 -90856479 653136155 83496076610803 489099759 364697492 82154832542014 -949875354 158616831 51048991661800 284569845 162945090 60967759780538 805526534 41572239 92317119301529 -307162093 915368399 111041273115626 -794806120 443...
output:
31919935866825
result:
ok single line: '31919935866825'
Test #74:
score: 17
Accepted
time: 229ms
memory: 45996kb
input:
200000 200000 3 144743 352871734 5 413265 -276869323 5 290482 -131298509 4 494650 -506969942 5 567208 287206022 5 5 399144334 1 362175 881619360 3 23912 724506439 5 570501 583130846 1 257386 -412498208 3 355302 228829348 2 572167 158906339 5 509728 -68005943 2 197839 774596778 4 286921 882307893 2 5...
output:
31231422581637
result:
ok single line: '31231422581637'
Subtask #8:
score: 9
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Test #75:
score: 9
Accepted
time: 854ms
memory: 182964kb
input:
1000000 1000000 126117083 488653800 -273869083 718209624 1497997444 -701209902 720605250 3044388034 -458745698 503507132 3928522989 -752337541 620116463 5243647752 -8066002 38631680 5525563658 -38238256 369456806 6181139840 -890483709 83051387 6479680762 -449872107 575805389 7761164090 -851209587 16...
output:
-249959330604131
result:
ok single line: '-249959330604131'
Test #76:
score: 9
Accepted
time: 504ms
memory: 113212kb
input:
1000000 1000000 47015483 956229305267217 -318352900 968545972 475621877 -838145315 912734744 1189126520 -802138552 462897372 1306928034 -690768481 920071607 725633315258449 -160413358 987486935 183743617 -944669900 486570279 793882777165464 -900188588 828518021 3546953620 -709373896 582676757 681621...
output:
-249637774723945
result:
ok single line: '-249637774723945'
Test #77:
score: 9
Accepted
time: 562ms
memory: 128820kb
input:
1000000 1000000 995396130 499666537652332 -1000000000 539384716 499666815480543 272 797054422 499667288560907 28 171809683 499666981953443 97 956735987 499667778398821 192 716100335 499668354924069 269 499070800 499668648546738 241 336858784 499668727715995 280 729582693 499669197559733 211 46943810...
output:
-167150129
result:
ok single line: '-167150129'
Test #78:
score: 9
Accepted
time: 1193ms
memory: 191496kb
input:
1000000 1000000 659055121 500021010425923 -289 295863189 500020681315696 -330 770965996 500021225186941 -319 173412763 500020911671750 -133 703368303 500020669586179 -268 761533950 500020673703265 -58 717600643 500020861835133 -108 904137324 500021518890244 -41 478820932 500021383562000 -56 83221529...
output:
-167015284
result:
ok single line: '-167015284'
Test #79:
score: 9
Accepted
time: 1549ms
memory: 140008kb
input:
1000000 1000000 908216743 202504871211765 815074999 558872235 406092775811330 488631364 413168085 131974698442193 955664469 967529927 499903590624517 521402379 452809628 465157718735705 688006065 821057591 432971418474925 152081890 898885998 290640922252444 441691511 802092172 495897779895573 875328...
output:
202063463357305
result:
ok single line: '202063463357305'
Test #80:
score: 9
Accepted
time: 891ms
memory: 107856kb
input:
1000000 934589 375430966 36823924 387997587 645867099 927229516 976866474 395607968 120490442520917 985362889 453979815 872613599 67499923 7774226 1051268307 439785823 165946017 122483597989393 368531834 160984227 278999555306379 963544682 319987971 354128029335973 147913869 76731574 347325541103656...
output:
127756295303467
result:
ok single line: '127756295303467'
Test #81:
score: 9
Accepted
time: 1085ms
memory: 130424kb
input:
892324 1000000 728344879 289072837203634 -107407387 363140912 469244215215798 137939188 145955904 436457316888782 -892099139 851893672 970279862282859 806777481 580170653 299922997002645 149380100 404196747 679357818211644 900708476 101651083 385401666037553 718649693 379159903 980062247066922 31280...
output:
236006357456318
result:
ok single line: '236006357456318'
Test #82:
score: 9
Accepted
time: 1448ms
memory: 139308kb
input:
1000000 1000000 1 735973 738092933 1 416560 101377061 1 263017 -658303804 1 784339 651770275 1 566532 437105081 1 515190 150336378 1 728513 596793704 1 479088 701500523 1 702471 705532766 1 961133 -865343418 1 794421 423833492 1 274352 514468862 1 62649 953661997 1 320479 -34079397 1 57966 364989651...
output:
252112613912371
result:
ok single line: '252112613912371'
Test #83:
score: 9
Accepted
time: 1446ms
memory: 135776kb
input:
1000000 1000000 652885 144453059524 -130816762 510455 378831316412 915577449 873513 27332886221 109736103 666030 295407070195 298210161 535093 497002911455 315971380 681335 484598868632 614408936 668646 321852048251 59900844 201605 693702856350 -788049486 848828 716913642470 176898611 571070 3485688...
output:
201708839726646
result:
ok single line: '201708839726646'
Extra Test:
score: 0
Extra Test Passed