QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786062 | #4963. Numbers on both Sides | LaVuna47# | AC ✓ | 96ms | 15164kb | C++20 | 3.7kb | 2024-11-26 20:07:05 | 2024-11-26 20:07:07 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
// segment tree with sum binary operation
struct SegTree
{
vector<ll> T;
int n;
// Root of the tree has index 1.
// Zero based indexing of A.
SegTree(const vector<ll>& A)
{
n = sz(A);
T = vector<ll>(2*n, 0);
for (int i = 0; i < n; ++i)
T[i+n] = A[i];
build();
}
SegTree(int nn)
{
this->n = nn;
T = vector<ll>(2*n, 0);
}
// [l; r)
ll query(int l, int r)
{
ll res = 0;
for(l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if(l & 1) res += T[l++];
if(r & 1) res += T[--r];
}
return res;
}
void add(int p, ll delta)
{
for (T[p += n] += delta; p > 1; p >>= 1)
T[p >> 1] = T[p] + T[p ^ 1];
}
void build()
{
for (int i = n-1; i >= 1; --i)
T[i] = T[i << 1] + T[i << 1 ^ 1];
}
};
int solve()
{
int n;
if(!(cin >> n))
return 1;
vector<ll> a(n);
vector<ll> b(n);
FOR(i,0,n) cin >> a[i];
FOR(i,0,n) cin >> b[i];
vector<ll> II(n+47);
{
unordered_map<ll, ll> I;
set<ll> S;
for(auto item: b)
S.insert(item);
int ctr = 1;
for(auto item: S)
I[item] = ctr++;
FOR(i,0,n)
{
II[i] = b[i];
b[i] = I[b[i]];
}
}
ll K, L;
cin >> K >> L;
ll as = 0;
SegTree segC(n+47), segS(n+47);
FOR(i,0,K) as += a[i], segC.add(b[i], 1), segS.add(b[i], II[i]);
auto query = [&]() -> ll {
int R = n+44;
int l = 0, r = n+44;
while(r-l>1)
{
int mid = (l+r)/2;
if(segC.query(mid,R) < L)
r = mid;
else
l = mid;
}
if(segC.query(r,R) < L)
l = r;
int t = l;
--t;
assert(segC.query(t,R) >= L);
assert(segC.query(t+1,R) < L);
if(segC.query(t, R) == L)
return segS.query(t,R);
int left = L-segC.query(t+1, R);
ll res = segS.query(t+1,R);
res += II[t]*left;
return res;
};
/*
5
1 1 2 3 4
1 2 3 4 5
5 5
*/
ll res = as+query();
//cout << "C = " << segC.query(0, n+44) << '\n';
//cout << "S = " << segS.query(0, n+44) << '\n';
//cout << query() << '\n';
for(int i = K-1, j = n-1; i >= 0; --i, --j)
{
as -= a[i];
as += a[j];
segC.add(b[i], -1);
segS.add(b[i], -II[i]);
segC.add(b[j], 1);
segS.add(b[j], II[j]);
res = max(res, as+query());
}
cout << res << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
5 9 7 2 2 9 5 2 2 3 1 2 1
output:
23
result:
ok single line: '23'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
5 9 7 2 2 9 5 9 2 3 1 2 1
output:
25
result:
ok single line: '25'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10 53580627 697780592 429665569 16172712 200486124 435516652 711503384 868083709 616939240 492192996 746044490 57589903 507886672 433841177 918380467 426664522 281530079 729659740 980794901 914640542 8 6
output:
8792267986
result:
ok single line: '8792267986'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
10 730481488 400954693 128613199 713199560 614447169 248941421 37750895 193920847 657063180 854828707 267000572 122726413 949085528 925195735 688098447 253874115 150107099 260234553 36890874 538579428 3 1
output:
2780952803
result:
ok single line: '2780952803'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 852820400 431554192 572868116 758571485 341275225 531674540 657702799 516837122 619205953 220596808 926702132 280512325 197693066 27979679 117338468 521804123 20171436 235111658 370713837 439200264 9 8
output:
8161548499
result:
ok single line: '8161548499'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
100 200840829 984371273 316878458 648198658 293687641 721383571 338507904 724997663 711458648 751691704 771452874 277466708 943807021 377360007 240332385 28339184 704140 374459938 492335941 101467194 409068487 932698864 779920580 433262346 898904826 540642521 653569283 127846153 551032330 12412920 1...
output:
37086240377
result:
ok single line: '37086240377'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
100 830016575 439934239 668877259 935247252 323206198 734611274 271059114 936566566 134792359 641293396 32104557 722386259 778373568 492415655 886679552 695943544 422212423 647550161 700095037 402972689 400096625 488007059 313475603 19821199 781311046 506111415 512673905 998124192 308609718 28036263...
output:
37743549974
result:
ok single line: '37743549974'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
100 858847955 585762265 461567328 709498722 115292217 175414056 179699389 245041464 479983922 817468345 879930461 174485488 421366165 327108892 610462034 706714 268070373 128579892 202198875 767530987 96230921 903605795 519326625 870839477 531183195 130976659 456994599 991749533 170204733 251820125 ...
output:
34327249560
result:
ok single line: '34327249560'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
200 848894068 441870488 843177200 476363989 227813785 935490332 536440332 800064223 820105099 132195551 654759987 591034963 60065055 705281083 34058541 333588512 346787808 965723739 38401782 79980517 910300657 594954685 253026985 764696039 201881480 418328493 545108862 253433648 41720808 904214857 5...
output:
34630078094
result:
ok single line: '34630078094'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
200 273865791 946682226 258167951 321428165 225071345 196925399 822138941 913265567 16675713 517291119 232071761 823967439 796726605 114919520 923556590 804450050 189841654 716962257 8035486 840023974 740902665 247289140 797455265 158029761 348213765 59863965 845784212 573430226 492553867 334645195 ...
output:
35333346618
result:
ok single line: '35333346618'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
200 881703801 673263976 481169602 174662798 868801960 689431486 341685232 319633614 440826513 613393860 884169195 867461189 92576606 790891018 508756871 287587691 660954485 618088423 760425986 644601852 428365199 928516643 90835066 250667853 214187375 475010298 648429412 193688777 997966770 74807740...
output:
36009322234
result:
ok single line: '36009322234'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
200 630755504 585772609 950745562 733599230 189207677 504760953 335275429 463989420 182732061 210262536 725093132 4344593 330397775 638591722 347971129 975068943 727735936 550897676 704386667 931484962 449043450 41726221 320357035 332696900 206857993 906365287 901562739 526044333 762881958 404440821...
output:
117088818029
result:
ok single line: '117088818029'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
200 717121608 965760558 227214713 180828704 271646365 787312658 994394422 212335985 625336583 368741096 666013659 198204700 776828164 103357689 138018646 439883933 107137086 893809098 685455386 943579911 921484726 802715712 958500914 498063742 105235693 529715996 99850422 444095374 126013579 5105478...
output:
120443621028
result:
ok single line: '120443621028'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
200 382913868 424379759 186550981 788255214 86199651 199162855 800361315 54830123 923755565 127830314 777657726 500894623 446930178 443749902 892360908 297541398 530683456 373610158 127147139 316232318 499726975 37516672 270499603 93796730 49764991 580552031 662281106 482166714 155430858 740574150 9...
output:
117551355352
result:
ok single line: '117551355352'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1000 454592864 620142109 114369295 415863961 156872895 49562862 79347120 232033083 720247096 534999124 532138243 761384558 645271049 314120426 45545021 117267929 338562398 271901752 344726883 45485015 339480258 611110302 609603232 84080922 81539135 776177945 466210390 819117406 286593939 389985526 3...
output:
903848359419
result:
ok single line: '903848359419'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1000 313200974 141780259 510129354 52129991 600925975 764398058 483536644 345279225 218800552 550008943 765681987 797068929 152826063 669649367 883696905 137661750 971887885 80426104 823780102 926881073 664561205 765987136 538202697 730721536 154933834 859694081 862818203 708844699 513711755 2313704...
output:
903469091105
result:
ok single line: '903469091105'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1000 159321931 433359732 809608785 384090683 81745763 350678467 795983559 730056058 207407074 998300589 578808698 990456541 723361156 186001477 224651101 120007285 772035061 24877952 431095370 139259099 715034385 924380662 709722198 755691309 598821031 598470267 81224175 508928801 458270631 86282926...
output:
899205616701
result:
ok single line: '899205616701'
Test #18:
score: 0
Accepted
time: 2ms
memory: 4680kb
input:
10000 668430778 897240623 683831471 667756397 150316814 915509418 620649485 911688890 368056425 930821617 536834872 40186839 264247174 112624421 458177539 81439427 3294615 613050009 740844417 186631957 829133920 696240520 119623080 104426222 526720733 334701907 342767198 623774047 430598591 97327692...
output:
2968301741831
result:
ok single line: '2968301741831'
Test #19:
score: 0
Accepted
time: 5ms
memory: 4900kb
input:
10000 679228878 703091840 852728745 452932462 129616227 802840354 628336850 863760230 44899009 918950060 415871441 108077060 565692993 201748078 38642803 265012703 680357418 795991543 325229312 147540642 422036563 704620134 467255917 265350917 815435738 569927376 460621803 213148806 933417838 266164...
output:
3157271164195
result:
ok single line: '3157271164195'
Test #20:
score: 0
Accepted
time: 6ms
memory: 4612kb
input:
10000 202526891 594981183 634309199 10038000 800959297 202532161 403217511 953914100 543521825 723940650 721147061 494637793 387360362 776951000 234948638 781738241 803240744 779329981 229149017 94703509 519036906 502867746 884489537 495864660 893426561 104951085 586658065 201287021 817224790 537860...
output:
3327361707292
result:
ok single line: '3327361707292'
Test #21:
score: 0
Accepted
time: 6ms
memory: 4764kb
input:
10000 640475155 248396809 786881953 715964798 93665124 835722006 154002407 160642522 284418659 965620409 612212017 563773612 570402327 200089275 912428957 883009713 768966294 36163154 831106002 709223328 531760258 745319531 504274165 673551652 411730290 137855384 493441658 941949731 335340177 698195...
output:
5264024200084
result:
ok single line: '5264024200084'
Test #22:
score: 0
Accepted
time: 7ms
memory: 4704kb
input:
10000 303256012 748175892 438095143 203240843 892719301 715930127 715678150 76609984 243101149 337266128 956033213 675434439 403243513 997225711 571084914 436084935 574588176 451851347 289714541 626151419 472209165 305206198 348799492 348880450 6425232 173395884 32269180 220553768 965087725 77005165...
output:
5309566411279
result:
ok single line: '5309566411279'
Test #23:
score: 0
Accepted
time: 7ms
memory: 4704kb
input:
10000 35210255 34733175 380401501 462308560 539862128 268666070 750802836 417283069 441486943 622682656 169148551 511186876 963193299 785759871 188851250 398300873 155486731 655355801 420131303 132920624 624519727 106306625 85242271 230888309 96400546 821553038 453836060 814862506 309883625 24687022...
output:
5208166165459
result:
ok single line: '5208166165459'
Test #24:
score: 0
Accepted
time: 59ms
memory: 14988kb
input:
100000 963284151 700490306 704761211 765367111 393335476 539775212 79683672 709518495 162353395 755929752 979987440 941770885 387975508 351239851 625486273 753997561 298276602 221512304 220394033 648749270 788920814 341333174 401636063 864598093 696067997 428019669 79537428 795760419 833260615 52495...
output:
2629478885037
result:
ok single line: '2629478885037'
Test #25:
score: 0
Accepted
time: 58ms
memory: 15116kb
input:
100000 960540281 561703832 876766380 776685388 825536720 686617847 687496447 385175733 490503571 765184506 581419475 404548577 219975420 619212078 847675550 145405545 851423790 154117198 289908963 413941138 381038712 328307638 672707823 52348978 370638164 419549592 191232330 775458907 162850187 5250...
output:
3453778925606
result:
ok single line: '3453778925606'
Test #26:
score: 0
Accepted
time: 54ms
memory: 15156kb
input:
100000 770905049 603243927 262208552 941341913 754659361 445383073 2642910 415824409 971119938 74479128 485738216 727999670 867553065 609625720 550428836 572414 301051096 196067891 334851819 206610442 630018824 754997790 775438830 133202768 921286173 45117266 813182648 492602661 269901170 255011533 ...
output:
5168785967630
result:
ok single line: '5168785967630'
Test #27:
score: 0
Accepted
time: 61ms
memory: 14924kb
input:
100000 64478312 340403114 170546625 518062147 45857589 488276348 747071633 702811394 523986564 360028510 678523499 795113294 496506706 56789347 157237265 559519140 279809647 784429412 202316024 546976071 412325378 558500135 548946093 664179230 320585104 113319793 970725399 804772521 582429148 379765...
output:
5981486433518
result:
ok single line: '5981486433518'
Test #28:
score: 0
Accepted
time: 55ms
memory: 15032kb
input:
100000 664408478 299046473 203010625 614061315 910074993 624685756 669581625 662217316 995569929 314990892 986655440 369507349 146275653 920540688 835880966 203192886 600141058 543775200 216315163 186798161 336448835 4477397 53182177 771561118 886996085 898188245 928778736 598499551 414557077 627284...
output:
8786371910856
result:
ok single line: '8786371910856'
Test #29:
score: 0
Accepted
time: 80ms
memory: 15028kb
input:
100000 735842453 84919500 682174908 114874536 555979042 495635630 2207543 681695345 987111850 602233453 542599123 483206320 552781674 927852683 706613876 310313767 276640986 934924255 700814937 401449943 509426145 350193254 263429678 567162495 665620087 345069957 550495538 708992700 278763254 510337...
output:
43800435000622
result:
ok single line: '43800435000622'
Test #30:
score: 0
Accepted
time: 96ms
memory: 14936kb
input:
100000 863073123 135478179 33849282 61113448 787902814 124686374 969132369 776918023 504292858 375028037 197746114 286386315 686225461 479249543 183816930 35523405 51760794 975347470 195901804 307982973 991386419 629945140 20019403 167294399 501847739 80864297 866984190 118055454 488087498 957139090...
output:
89279962109831
result:
ok single line: '89279962109831'
Test #31:
score: 0
Accepted
time: 96ms
memory: 14936kb
input:
100000 244446505 957765306 277484938 561252249 980916830 934400410 900348696 295198665 317017184 667024040 354198458 474134 177701844 419802577 593893806 932500379 412084260 402602342 201277364 42874323 94612536 659017500 784921160 635069750 774508069 238062261 941816917 540448753 623921383 13982806...
output:
89813913986660
result:
ok single line: '89813913986660'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
100 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 231 241 251 261 271 281 291 301 311 321 331 341 351 361 371 381 391 401 411 421 431 441 451 461 471 481 491 501 511 521 531 541 551 561 571 581 591 601 611 621 631 641 651 661 671 681 691 701 711 721 731 741 751 761...
output:
59075
result:
ok single line: '59075'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
100 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 231 241 251 261 271 281 291 301 311 321 331 341 351 361 371 381 391 401 411 421 431 441 451 461 471 481 491 501 511 521 531 541 551 561 571 581 591 601 611 621 631 641 651 661 671 681 691 701 711 721 731 741 751 761...
output:
25000021800
result:
ok single line: '25000021800'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
100 1000000000 999999990 999999980 999999970 999999960 999999950 999999940 999999930 999999920 999999910 999999900 999999890 999999880 999999870 999999860 999999850 999999840 999999830 999999820 999999810 999999800 999999790 999999780 999999770 999999760 999999750 999999740 999999730 999999720 99999...
output:
49999997025
result:
ok single line: '49999997025'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 1000000000 999999990 999999980 999999970 999999960 999999950 999999940 999999930 999999920 999999910 999999900 999999890 999999880 999999870 999999860 999999850 999999840 999999830 999999820 999999810 999999800 999999790 999999780 999999770 999999760 999999750 999999740 999999730 999999720 99999...
output:
74999984750
result:
ok single line: '74999984750'
Test #36:
score: 0
Accepted
time: 76ms
memory: 14988kb
input:
100000 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 231 241 251 261 271 281 291 301 311 321 331 341 351 361 371 381 391 401 411 421 431 441 451 461 471 481 491 501 511 521 531 541 551 561 571 581 591 601 611 621 631 641 651 661 671 681 691 701 711 721 731 741 751 ...
output:
97499320000
result:
ok single line: '97499320000'
Test #37:
score: 0
Accepted
time: 63ms
memory: 15036kb
input:
100000 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201 211 221 231 241 251 261 271 281 291 301 311 321 331 341 351 361 371 381 391 401 411 421 431 441 451 461 471 481 491 501 511 521 531 541 551 561 571 581 591 601 611 621 631 641 651 661 671 681 691 701 711 721 731 741 751 ...
output:
80009500040000
result:
ok single line: '80009500040000'
Test #38:
score: 0
Accepted
time: 77ms
memory: 15152kb
input:
100000 1000000000 999999990 999999980 999999970 999999960 999999950 999999940 999999930 999999920 999999910 999999900 999999890 999999880 999999870 999999860 999999850 999999840 999999830 999999820 999999810 999999800 999999790 999999780 999999770 999999760 999999750 999999740 999999730 999999720 99...
output:
89999500130000
result:
ok single line: '89999500130000'
Test #39:
score: 0
Accepted
time: 74ms
memory: 15164kb
input:
100000 1000000000 999999990 999999980 999999970 999999960 999999950 999999940 999999930 999999920 999999910 999999900 999999890 999999880 999999870 999999860 999999850 999999840 999999830 999999820 999999810 999999800 999999790 999999780 999999770 999999760 999999750 999999740 999999730 999999720 99...
output:
169927500850000
result:
ok single line: '169927500850000'