ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#702 | #114. 【0621 模拟赛】Vrsta | protractor | 100 | 16487ms | 44188kb | C++14 | 1.0kb | 2025-06-21 16:19:41 | 2025-06-21 23:52:56 |
answer
#include<iostream>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int v[2000050];
long long a[2000050];
int b[2000050];
struct{
int l,r;
long long d;
}t[8000050];
int n;
long long sum;
int p[2000050],cnt;
map<int,int> m;
void init(int id,int l,int r)
{
t[id].l=l,t[id].r=r;
if(r-l)
{
int mid=(l+r)/2;
init(id*2,l,mid);
init(id*2+1,mid+1,r);
}
}
void plu(int id,int x,long long y)
{
if(t[id].l<=x&&x<=t[id].r)
{
t[id].d+=y;
plu(id*2,x,y);
plu(id*2+1,x,y);
}
}
int cha(int id,long long x,long long sum)
{
if(t[id].r-t[id].l==0) return t[id].l;
if(t[id*2].d+sum>=x) return cha(id*2,x,sum);
else return cha(id*2+1,x,sum+t[id*2].d);
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>a[i];
b[i]=v[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
if(b[i]-b[i-1])
{
p[++cnt]=b[i];
m[b[i]]=cnt;
}
}
init(1,1,cnt);
for(int i=1;i<=n;i++)
{
sum+=a[i];
plu(1,m[v[i]],a[i]);
cout<<p[cha(1,(sum+1)/2,0)]<<'\n';
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 17
Accepted
Test #1:
score: 17
Accepted
time: 1ms
memory: 11588kb
input:
1000 301 524 526 970 675 623 471 905 266 808 513 31 228 393 565 377 840 936 986 540 288 112 868 454 ...
output:
301 526 526 526 471 471 471 471 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 565 ...
result:
ok 1000 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 11624kb
input:
1000 992 520 931 696 697 642 99 589 925 757 164 511 910 966 588 171 130 378 682 7 541 673 711 127 11...
output:
992 931 931 697 925 925 910 910 910 910 697 711 711 697 588 541 541 541 541 541 529 541 529 529 301 ...
result:
ok 1000 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 11700kb
input:
1000 606 804 707 15 557 937 701 888 304 721 536 876 100 658 766 528 276 601 321 343 971 584 510 259 ...
output:
606 606 557 606 606 557 557 557 557 536 557 557 536 536 536 557 557 557 536 536 536 536 536 536 536 ...
result:
ok 1000 tokens
Test #4:
score: 0
Accepted
time: 2ms
memory: 11592kb
input:
1000 345 467 626 777 650 974 445 736 534 279 612 166 466 47 213 213 378 703 351 207 157 370 387 357 ...
output:
345 626 626 626 626 626 626 612 534 445 445 445 445 445 445 445 445 445 445 514 445 445 443 445 445 ...
result:
ok 1000 tokens
Test #5:
score: 0
Accepted
time: 0ms
memory: 11704kb
input:
1000 159 540 375 589 969 94 4 997 402 811 810 900 937 542 631 410 610 587 175 498 412 45 194 199 621...
output:
159 375 375 159 159 375 402 402 402 402 402 402 402 402 375 375 375 402 402 494 402 494 402 494 402 ...
result:
ok 1000 tokens
Test #6:
score: 0
Accepted
time: 0ms
memory: 11604kb
input:
1000 916 421 384 855 594 508 608 633 531 155 197 577 59 511 740 347 117 329 863 264 783 932 627 927 ...
output:
916 384 594 594 594 531 384 531 384 531 594 608 608 594 594 594 594 594 594 608 608 608 608 608 608 ...
result:
ok 1000 tokens
Test #7:
score: 0
Accepted
time: 1ms
memory: 11676kb
input:
1000 765 434 277 734 119 877 85 404 796 37 463 629 862 372 91 106 408 12 436 725 176 888 584 503 566...
output:
765 277 277 119 119 277 277 277 277 436 277 277 436 277 436 398 436 436 436 436 436 463 463 463 463 ...
result:
ok 1000 tokens
Test #8:
score: 0
Accepted
time: 1ms
memory: 11592kb
input:
1000 718 891 157 720 643 677 560 563 996 328 907 4 162 164 76 918 61 120 776 359 240 440 84 708 342 ...
output:
718 718 643 643 643 643 643 560 560 560 560 240 240 560 494 560 560 643 593 593 593 643 597 597 597 ...
result:
ok 1000 tokens
Test #9:
score: 0
Accepted
time: 1ms
memory: 11640kb
input:
1000 769 996 417 964 639 257 50 71 776 253 511 728 671 316 654 253 940 609 463 756 165 646 123 316 5...
output:
769 769 639 639 639 511 639 639 654 639 511 511 511 511 511 511 511 511 511 581 639 581 581 639 639 ...
result:
ok 1000 tokens
Test #10:
score: 0
Accepted
time: 3ms
memory: 11740kb
input:
1000 924 481 585 955 526 387 581 655 717 108 764 262 378 781 349 402 878 764 985 629 366 839 238 927...
output:
924 585 585 585 585 585 581 581 585 585 585 581 581 581 581 585 585 585 585 585 585 585 585 585 581 ...
result:
ok 1000 tokens
Subtask #2:
score: 24
Accepted
Test #11:
score: 24
Accepted
time: 439ms
memory: 44028kb
input:
200000 256026126 1 892260323 1 695786111 1 211630710 1 117439167 1 462551546 1 999465877 1 173326801...
output:
256026126 256026126 695786111 256026126 256026126 256026126 462551546 256026126 462551546 462551546 ...
result:
ok 200000 tokens
Test #12:
score: 0
Accepted
time: 450ms
memory: 43888kb
input:
200000 511062531 1 742906051 1 232871947 1 955443599 1 463714572 1 249211017 1 447124029 1 278917899...
output:
511062531 511062531 511062531 511062531 511062531 463714572 463714572 447124029 463714572 447124029 ...
result:
ok 200000 tokens
Test #13:
score: 0
Accepted
time: 444ms
memory: 44188kb
input:
200000 847271014 1 390732980 1 117278113 1 636102884 1 214952923 1 872245315 1 409748707 1 517292053...
output:
847271014 390732980 390732980 390732980 390732980 390732980 409748707 409748707 416474923 416474923 ...
result:
ok 200000 tokens
Test #14:
score: 0
Accepted
time: 438ms
memory: 44024kb
input:
200000 374231771 1 140075164 1 914553974 1 338596787 1 481913895 1 770050227 1 450298538 1 721883916...
output:
374231771 140075164 374231771 338596787 374231771 374231771 450298538 450298538 481913895 450298538 ...
result:
ok 200000 tokens
Test #15:
score: 0
Accepted
time: 448ms
memory: 44072kb
input:
200000 869635202 1 799391576 1 602811955 1 167889679 1 308606348 1 215296991 1 417026130 1 840641456...
output:
869635202 799391576 799391576 602811955 602811955 308606348 417026130 417026130 602811955 602811955 ...
result:
ok 200000 tokens
Test #16:
score: 0
Accepted
time: 441ms
memory: 44116kb
input:
200000 443033894 1 815780580 1 265569714 1 332527543 1 164657165 1 705234273 1 595443540 1 969642368...
output:
443033894 443033894 443033894 332527543 332527543 332527543 443033894 443033894 443033894 332527543 ...
result:
ok 200000 tokens
Test #17:
score: 0
Accepted
time: 447ms
memory: 44048kb
input:
200000 382634462 1 481215065 1 219831549 1 29022542 1 768832692 1 185478405 1 756708637 1 390652308 ...
output:
382634462 382634462 382634462 219831549 382634462 219831549 382634462 382634462 390652308 390652308 ...
result:
ok 200000 tokens
Test #18:
score: 0
Accepted
time: 446ms
memory: 44032kb
input:
200000 524032424 1 363204028 1 307783573 1 808820938 1 102044336 1 507749222 1 940720344 1 292479917...
output:
524032424 363204028 363204028 363204028 363204028 363204028 507749222 363204028 507749222 507749222 ...
result:
ok 200000 tokens
Test #19:
score: 0
Accepted
time: 441ms
memory: 43996kb
input:
200000 723528666 1 727167549 1 971090839 1 507046596 1 801343240 1 927296032 1 827160578 1 330253033...
output:
723528666 723528666 727167549 723528666 727167549 727167549 801343240 727167549 727167549 727167549 ...
result:
ok 200000 tokens
Test #20:
score: 0
Accepted
time: 447ms
memory: 44152kb
input:
200000 439550710 1 27858030 1 793244466 1 575428164 1 238983290 1 66985464 1 627581205 1 942941442 1...
output:
439550710 27858030 439550710 439550710 439550710 238983290 439550710 439550710 439550710 238983290 4...
result:
ok 200000 tokens
Subtask #3:
score: 26
Accepted
Test #21:
score: 26
Accepted
time: 317ms
memory: 44036kb
input:
200000 494956245 468045996 541938782 655353528 759612619 212790460 910600435 776972542 996033636 890...
output:
494956245 541938782 541938782 541938782 910600435 910600435 996033636 996033636 996033636 996033636 ...
result:
ok 200000 tokens
Test #22:
score: 0
Accepted
time: 314ms
memory: 44032kb
input:
200000 171764444 140068816 243748900 914437683 487432414 134509998 992611085 880468785 994886132 430...
output:
171764444 243748900 243748900 243748900 992611085 992611085 992611085 992611085 994886132 994886132 ...
result:
ok 200000 tokens
Test #23:
score: 0
Accepted
time: 310ms
memory: 44140kb
input:
200000 765447789 980324791 901803205 870527420 941153393 339142062 994588437 99606005 995046654 1180...
output:
765447789 765447789 901803205 901803205 901803205 901803205 901803205 901803205 941153393 996734605 ...
result:
ok 200000 tokens
Test #24:
score: 0
Accepted
time: 308ms
memory: 44080kb
input:
200000 112731270 253096166 348093357 54336253 883178259 633690613 898549709 48028362 995788098 75846...
output:
112731270 112731270 883178259 883178259 883178259 883178259 995788098 995788098 995788098 995788098 ...
result:
ok 200000 tokens
Test #25:
score: 0
Accepted
time: 314ms
memory: 44044kb
input:
200000 861759763 816220321 867865302 732300695 918153443 673392435 990373491 113118535 996341472 618...
output:
861759763 861759763 867865302 867865302 867865302 918153443 918153443 918153443 990373491 990373491 ...
result:
ok 200000 tokens
Test #26:
score: 0
Accepted
time: 304ms
memory: 44072kb
input:
200000 911181934 495985330 996957718 198016095 998483749 992095854 999141386 689849196 999152807 844...
output:
911181934 911181934 998483749 998483749 998483749 999141386 999141386 999152807 999152807 999617962 ...
result:
ok 200000 tokens
Test #27:
score: 0
Accepted
time: 310ms
memory: 44084kb
input:
200000 576130751 16139601 631718053 115699344 805902467 913205194 825140570 347324727 914524771 3616...
output:
576130751 631718053 805902467 805902467 805902467 825140570 914524771 926933805 926933805 926933805 ...
result:
ok 200000 tokens
Test #28:
score: 0
Accepted
time: 302ms
memory: 44032kb
input:
200000 699097559 531945914 763416695 495790120 963834852 606926877 979773694 79019177 989801086 5064...
output:
699097559 699097559 763416695 763416695 763416695 763416695 963834852 963834852 963834852 963834852 ...
result:
ok 200000 tokens
Test #29:
score: 0
Accepted
time: 314ms
memory: 44076kb
input:
200000 525635141 46448056 858472506 644389397 875565492 57949438 875836858 195074052 939973400 36848...
output:
525635141 858472506 858472506 858472506 858472506 858472506 875565492 939973400 939973400 939973400 ...
result:
ok 200000 tokens
Test #30:
score: 0
Accepted
time: 317ms
memory: 44044kb
input:
200000 934495864 924548475 969486408 755595129 984581412 390850232 992649055 283990549 994097043 835...
output:
934495864 934495864 969486408 969486408 969486408 984581412 984581412 994097043 994097043 994097043 ...
result:
ok 200000 tokens
Subtask #4:
score: 33
Accepted
Test #31:
score: 33
Accepted
time: 491ms
memory: 43960kb
input:
200000 422540597 176760020 689401725 827252905 846177590 973043804 957312410 898620634 779222133 631...
output:
422540597 689401725 689401725 846177590 846177590 846177590 846177590 846177590 830439857 830439857 ...
result:
ok 200000 tokens
Test #32:
score: 0
Accepted
time: 508ms
memory: 43960kb
input:
200000 966913885 940780116 555898026 596993403 265189076 878846679 507962397 830338906 108357835 938...
output:
966913885 966913885 555898026 507962397 507962397 507962397 507962397 265189076 265189076 265189076 ...
result:
ok 200000 tokens
Test #33:
score: 0
Accepted
time: 493ms
memory: 43956kb
input:
200000 736054527 29547839 107142847 694365394 983756251 873605462 618103500 256892841 546694344 4001...
output:
736054527 107142847 983756251 618103500 618103500 889266718 618103500 180549831 180549831 180549831 ...
result:
ok 200000 tokens
Test #34:
score: 0
Accepted
time: 496ms
memory: 44028kb
input:
200000 123513212 629971890 566394695 113036133 850909360 277952527 336892570 335440516 533433808 139...
output:
123513212 123513212 123513212 336892570 336892570 533433808 212098075 533433808 336892570 295953247 ...
result:
ok 200000 tokens
Test #35:
score: 0
Accepted
time: 503ms
memory: 44180kb
input:
200000 597376443 964993614 952881745 828005828 496921417 128633068 8089921 928527470 110156513 19765...
output:
597376443 597376443 597376443 597376443 597376443 496921417 597376443 597376443 597376443 597376443 ...
result:
ok 200000 tokens
Test #36:
score: 0
Accepted
time: 506ms
memory: 43980kb
input:
200000 198090439 961763328 562162647 566963134 836050247 805003553 799426116 861523991 788024684 293...
output:
198090439 198090439 562162647 799426116 788024684 788024684 562162647 562162647 562162647 562162647 ...
result:
ok 200000 tokens
Test #37:
score: 0
Accepted
time: 505ms
memory: 44116kb
input:
200000 974737059 308627099 525599372 503886617 13711487 816907081 557211738 868778014 69606212 19207...
output:
974737059 525599372 13711487 525599372 525599372 525599372 366136549 366136549 525599372 525599372 5...
result:
ok 200000 tokens
Test #38:
score: 0
Accepted
time: 506ms
memory: 44032kb
input:
200000 380902927 71052410 953861848 245647090 470766136 570394247 948671356 146484069 960841441 1232...
output:
380902927 953861848 470766136 470766136 470766136 470766136 508725001 470766136 508725001 508725001 ...
result:
ok 200000 tokens
Test #39:
score: 0
Accepted
time: 504ms
memory: 44136kb
input:
200000 904922290 108104672 601025750 550599488 11454032 261681870 218115617 123337756 721147397 4616...
output:
904922290 601025750 601025750 601025750 601025750 432068378 432068378 432068378 432068378 432068378 ...
result:
ok 200000 tokens
Test #40:
score: 0
Accepted
time: 502ms
memory: 43988kb
input:
200000 286664495 848052348 223515789 43888473 995256719 131930115 882401029 373265515 944268061 2546...
output:
286664495 286664495 286664495 286664495 286664495 286664495 286664495 286664495 465999138 465999138 ...
result:
ok 200000 tokens
Test #41:
score: 0
Accepted
time: 490ms
memory: 43976kb
input:
200000 931960194 514407826 9371170 18439012 272758492 335684859 776494001 95631846 737336076 3852859...
output:
931960194 931960194 931960194 931960194 737336076 737336076 449724798 737336076 768703572 737336076 ...
result:
ok 200000 tokens
Test #42:
score: 0
Accepted
time: 498ms
memory: 43964kb
input:
200000 745548390 546673768 272218118 625981766 986413691 327823936 487064866 501465235 646678443 799...
output:
745548390 272218118 745548390 487064866 646678443 646678443 646678443 487064866 646678443 646678443 ...
result:
ok 200000 tokens
Test #43:
score: 0
Accepted
time: 496ms
memory: 43968kb
input:
200000 9436272 80311956 823723969 539569443 556945376 580615934 957689206 395810267 52152838 3413109...
output:
9436272 823723969 556945376 823723969 556945376 823723969 556945376 556945376 556945376 600591044 55...
result:
ok 200000 tokens
Test #44:
score: 0
Accepted
time: 493ms
memory: 44032kb
input:
200000 186672594 577091436 659845006 314719178 852300233 138736843 661142931 758410821 887606639 314...
output:
186672594 186672594 186672594 661142931 661142931 661142931 324856005 659845006 659845006 530746301 ...
result:
ok 200000 tokens
Test #45:
score: 0
Accepted
time: 326ms
memory: 30920kb
input:
200000 138386839 1 769028500 1 736442669 1 775085411 1 387034565 1 503337099 1 888772673 1 305595917...
output:
138386839 138386839 736442669 736442669 736442669 503337099 736442669 503337099 503337099 503337099 ...
result:
ok 200000 tokens
Test #46:
score: 0
Accepted
time: 318ms
memory: 30788kb
input:
200000 542754458 1 2727046 1 224156901 1 761042839 1 804300507 1 408814207 1 262669320 1 315274431 1...
output:
542754458 2727046 224156901 224156901 542754458 408814207 408814207 315274431 408814207 315274431 40...
result:
ok 200000 tokens
Test #47:
score: 0
Accepted
time: 317ms
memory: 30792kb
input:
200000 236420822 1 80873369 1 677229475 1 199994887 1 948006659 1 158866791 1 229324977 1 303586887 ...
output:
236420822 80873369 236420822 199994887 236420822 199994887 229324977 229324977 234157034 234157034 2...
result:
ok 200000 tokens
Test #48:
score: 0
Accepted
time: 325ms
memory: 30812kb
input:
200000 872829041 1 59383532 1 624117379 1 249873314 1 203063843 1 311346131 1 79968448 1 22624268 1 ...
output:
872829041 59383532 624117379 249873314 249873314 249873314 249873314 203063843 249873314 203063843 2...
result:
ok 200000 tokens
Test #49:
score: 0
Accepted
time: 322ms
memory: 30908kb
input:
200000 792146822 1 274485037 1 853347178 1 791300499 1 94108349 1 658561761 1 215194849 1 493184284 ...
output:
792146822 274485037 792146822 791300499 791300499 658561761 658561761 493184284 493184284 278599311 ...
result:
ok 200000 tokens
Test #50:
score: 0
Accepted
time: 324ms
memory: 30864kb
input:
200000 212024815 1 537505392 1 255143524 1 164488400 1 767976946 1 677057181 1 468911535 1 254686406...
output:
212024815 212024815 255143524 212024815 255143524 255143524 468911535 255143524 468911535 468911535 ...
result:
ok 200000 tokens