QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#782900 | #5513. Advertisement 2 | _lax | 100 ✓ | 987ms | 43648kb | C++20 | 1.8kb | 2024-11-25 22:04:33 | 2024-11-25 22:04:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;
const ll bs = 370;
#define bit(x,y) ((x >> y) & 1)
ll n;
pair<ll,ll> a[N];
pair<ll,ll> b[N];
ll bl[N],l[N],r[N],lzl[N],lzr[N],haha[N];
ll get(ll id)
{
ll bid = bl[id];
return max(haha[id],max(lzl[bid] - (a[id].first - a[l[bid]].first),lzr[bid] - (a[r[bid]].first - a[id].first)));
}
int main()
{
ll i,j;
cin >> n;
for(i = 1;i <= n;i++)
{
cin >> a[i].first >> a[i].second;
}
sort(a + 1,a + 1 + n);
ll m = 0;
for(i = 1;i <= n;i += bs)
{
++m;
l[m] = i;
r[m] = min(n,i + bs - 1);
lzl[m] = lzr[m] = -inf;
for(j = l[m];j <= r[m];j++)
{
bl[j] = m;
haha[j] = -inf;
}
}
for(i = 1;i <= n;i++)
{
b[i] = {a[i].second,i};
}
sort(b + 1,b + 1 + n,greater<pair<ll,ll>>());
ll ans = 0;
for(i = 1;i <= n;i++)
{
if(get(b[i].second) >= b[i].first) continue;
ans++;
ll id = b[i].second;
ll bid = bl[id];
haha[id] = max(haha[id],b[i].first);
for(j = id - 1;j >= l[bid];j--)
{
haha[j] = max(haha[j],b[i].first - (a[id].first - a[j].first));
}
for(j = id + 1;j <= r[bid];j++)
{
haha[j] = max(haha[j],b[i].first - (a[j].first - a[id].first));
}
for(j = bid - 1;j >= 1;j--)
{
lzr[j] = max(lzr[j],b[i].first - (a[id].first - a[r[j]].first));
}
for(j = bid + 1;j <= m;j++)
{
lzl[j] = max(lzl[j],b[i].first - (a[l[j]].first - a[id].first));
}
}
cout << ans;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 126ms
memory: 26532kb
input:
128800 9199612 51970557 152303663 51970557 658020283 51970557 305169975 51970557 647937895 51970557 162441995 51970557 664350717 51970557 128813867 51970557 815800777 51970557 422654970 51970557 5325941 51970557 919605369 51970557 775929588 51970557 957253076 51970557 441558150 51970557 730596606 51...
output:
116732
result:
ok single line: '116732'
Test #2:
score: 10
Accepted
time: 150ms
memory: 26700kb
input:
178516 481507914 185523732 434623365 185523732 472444125 185523732 759573017 185523732 253426284 185523732 700756636 185523732 74218273 185523732 978855318 185523732 193027753 185523732 670445963 185523732 647115447 185523732 355737335 185523732 213219833 185523732 580124162 185523732 361750049 1855...
output:
77180
result:
ok single line: '77180'
Test #3:
score: 10
Accepted
time: 270ms
memory: 40740kb
input:
462572 101498948 303922224 642297835 303922224 417145698 303922224 889349783 303922224 434461522 303922224 93863358 303922224 215632530 303922224 832856402 303922224 703199983 303922224 809081237 303922224 557497978 303922224 655494326 303922224 195187810 303922224 812819691 303922224 814441567 3039...
output:
4625
result:
ok single line: '4625'
Test #4:
score: 10
Accepted
time: 170ms
memory: 36060kb
input:
325752 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840273835 619184372 840...
output:
1
result:
ok single line: '1'
Test #5:
score: 10
Accepted
time: 987ms
memory: 41468kb
input:
500000 432233751 37126744 876209848 37126744 115636122 37126744 722895189 37126744 385407335 37126744 631777770 37126744 640127217 37126744 850533001 37126744 857281519 37126744 47214872 37126744 67273107 37126744 817606002 37126744 197019377 37126744 816304624 37126744 780928469 37126744 991314112 ...
output:
453173
result:
ok single line: '453173'
Test #6:
score: 10
Accepted
time: 626ms
memory: 42020kb
input:
500000 347979517 402569575 240027608 402569575 984267933 402569575 490577061 402569575 248258763 402569575 866530973 402569575 301265202 402569575 736701829 402569575 47460490 402569575 878566519 402569575 485021670 402569575 978430003 402569575 530094575 402569575 51797713 402569575 975446346 40256...
output:
216136
result:
ok single line: '216136'
Test #7:
score: 10
Accepted
time: 299ms
memory: 42072kb
input:
500000 394843641 428581569 931365318 428581569 205656498 428581569 325306857 428581569 567772605 428581569 495792279 428581569 521260039 428581569 275722970 428581569 168204637 428581569 882738248 428581569 211294121 428581569 236121938 428581569 498382424 428581569 406387147 428581569 664092862 428...
output:
5000
result:
ok single line: '5000'
Test #8:
score: 10
Accepted
time: 257ms
memory: 42124kb
input:
500000 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502907510 180068482 502...
output:
1
result:
ok single line: '1'
Subtask #2:
score: 23
Accepted
Test #9:
score: 23
Accepted
time: 0ms
memory: 17904kb
input:
3 231636235 354089104 228392707 930073348 587735804 575683740
output:
2
result:
ok single line: '2'
Test #10:
score: 23
Accepted
time: 2ms
memory: 17976kb
input:
2 44803615 325394921 960290812 913042209
output:
2
result:
ok single line: '2'
Test #11:
score: 23
Accepted
time: 0ms
memory: 17912kb
input:
16 358962202 959156048 292228464 457977429 286504790 688097514 10235865 287544591 543037593 223202351 281739475 678894125 340538778 135823278 523049160 699098750 632448464 27592532 678838907 280282008 232201876 610344934 372201424 580697311 534022553 149440684 396794335 231096472 386573567 674797431...
output:
1
result:
ok single line: '1'
Test #12:
score: 23
Accepted
time: 0ms
memory: 18064kb
input:
16 991478601 586353863 727677584 413218995 848190574 721774939 337154838 587621991 326181535 330546474 885714927 902337871 321925936 254469460 389203245 713455202 269046070 768322315 614176036 221983130 199199666 945777980 333801969 632191948 426251079 645513607 230568723 962651792 817646607 6209057...
output:
3
result:
ok single line: '3'
Test #13:
score: 23
Accepted
time: 1ms
memory: 17896kb
input:
16 259716405 81082178 865953834 204158972 701456061 326495636 534687353 313425011 649435476 973258810 655435866 100458236 842552753 181656857 473079491 116991153 2508936 173927847 405046133 391068638 302771733 495790124 35966251 515357032 272182509 442914085 348221691 938487780 990378664 943640991 2...
output:
3
result:
ok single line: '3'
Test #14:
score: 23
Accepted
time: 1ms
memory: 17856kb
input:
16 750613470 787418986 170979548 365164484 538034539 608096710 860751449 225707539 484373402 547435035 940351136 194668865 912301765 93898337 458896779 93991117 604496090 637207865 887366195 906979783 557233961 724709014 79115098 854994617 46404315 744331005 915505818 998759323 415682887 70000722 24...
output:
3
result:
ok single line: '3'
Test #15:
score: 23
Accepted
time: 1ms
memory: 17852kb
input:
16 4 4 12 10 7 1 14 9 5 1 7 4 6 2 11 12 11 8 7 7 1 16 1 7 7 11 10 1 5 9 16 14
output:
4
result:
ok single line: '4'
Test #16:
score: 23
Accepted
time: 0ms
memory: 18052kb
input:
16 14 11 15 15 2 2 9 11 12 3 1 2 5 6 3 8 11 6 6 8 16 8 7 13 14 15 3 9 11 13 5 12
output:
5
result:
ok single line: '5'
Test #17:
score: 23
Accepted
time: 0ms
memory: 17904kb
input:
16 658226792 613575956 913043019 676526283 924694003 969774080 131921851 969262560 105914395 172872671 871392287 24274699 165576907 264780282 21100418 923953766 624953565 298094995 530525465 571735572 303994035 463877704 809045037 954969312 573298570 667280152 101731595 308198144 530525465 554053924...
output:
4
result:
ok single line: '4'
Test #18:
score: 23
Accepted
time: 2ms
memory: 17904kb
input:
16 41059816 221337331 83624488 326689210 104858222 385883720 404619929 86122013 634866221 167428105 333552651 862965438 254015874 434293389 326707158 747676654 450873607 69675126 443566588 47175354 634866221 532361838 611136129 921561993 859951785 430454936 166920241 409984963 634866221 611154765 45...
output:
3
result:
ok single line: '3'
Test #19:
score: 23
Accepted
time: 2ms
memory: 17908kb
input:
16 936303273 104982189 63575875 559779062 796436147 569999950 688713338 829608600 54555214 355061353 213704891 195911676 392107461 17509106 922762043 308356453 301430216 797633403 991422839 48500064 287802278 121814289 172394178 237222389 688713338 135188143 633629597 30839372 564890892 276172238 68...
output:
2
result:
ok single line: '2'
Test #20:
score: 23
Accepted
time: 0ms
memory: 17976kb
input:
16 357789622 471544489 155990470 269745335 398736883 512491748 873381940 675455361 693445929 807200795 819730274 729107023 609830064 723584926 909092208 639745095 717541218 831296078 384480802 498235672 255651917 369406780 368140959 481895828 478227819 591982683 939144255 609693050 40813895 15456875...
output:
8
result:
ok single line: '8'
Test #21:
score: 23
Accepted
time: 1ms
memory: 17908kb
input:
16 675342555 193353548 971242060 11 536846016 331850093 836414885 32281218 186149471 245161906 928775073 8 750901538 117794571 828962292 39733819 911644130 4 588800258 279895844 296580159 355592604 802169978 66526131 273197350 332209795 404841833 463854267 109933975 168946414 885435693 10
output:
8
result:
ok single line: '8'
Test #22:
score: 23
Accepted
time: 1ms
memory: 18060kb
input:
16 953262221 724605861 954831951 723036137 687777113 990090964 350416397 707784111 683740929 986054786 599178111 901491972 585162338 898281936 692323709 985544379 525093723 882461438 557373498 914741210 584165982 899278291 203656094 561023816 854238442 823629640 278833052 636200772 577917599 8941971...
output:
11
result:
ok single line: '11'
Test #23:
score: 23
Accepted
time: 1ms
memory: 18004kb
input:
16 254025469 306467199 427159560 479601287 593614318 571659026 928541548 665993610 896411728 698123427 892481215 694192919 63151125 115592847 986723922 607811241 499586562 552028289 556415811 608857532 293855819 346297542 128409262 180850989 763105705 574193679 238718076 291159807 101875941 15431766...
output:
11
result:
ok single line: '11'
Subtask #3:
score: 36
Accepted
Dependency #2:
100%
Accepted
Test #24:
score: 36
Accepted
time: 0ms
memory: 18020kb
input:
969 40204287 456937654 286592935 721399309 55601488 988576547 98308463 233903868 372607004 249568606 671927697 865318354 859455683 411992226 204457272 180441733 613470249 214734085 527175838 697833267 358494964 102583786 46530087 943520460 253765364 851932504 364762894 237641176 205684131 478882150 ...
output:
24
result:
ok single line: '24'
Test #25:
score: 36
Accepted
time: 3ms
memory: 17924kb
input:
1000 880013645 976496466 168891871 397610144 959197196 125720324 380287625 176707789 235251414 829738258 104084949 866030971 885816763 465601987 395087567 530405853 876284097 789067453 203022779 708307028 636370005 324881466 861428789 197553177 198453322 241450195 90198257 673639529 834173260 269328...
output:
32
result:
ok single line: '32'
Test #26:
score: 36
Accepted
time: 0ms
memory: 18040kb
input:
1000 533 645 74 453 769 779 793 353 761 921 729 839 457 996 605 541 645 842 322 384 250 332 9 939 401 754 130 426 146 969 997 151 793 39 328 725 204 777 975 532 13 884 202 320 762 18 759 217 451 413 585 155 473 328 276 86 40 252 636 146 106 870 666 159 642 322 988 776 49 671 890 338 128 554 117 509 ...
output:
27
result:
ok single line: '27'
Test #27:
score: 36
Accepted
time: 2ms
memory: 17916kb
input:
1000 600153103 736357270 88040510 941572196 602021946 377693696 269174942 944477478 820146987 527363023 843579567 779423993 912584532 969101909 14984782 25263181 252185481 700823545 974849508 252152945 984874904 852521251 668548631 720271023 330490714 733028069 725617593 832434531 644861751 32287606...
output:
36
result:
ok single line: '36'
Test #28:
score: 36
Accepted
time: 2ms
memory: 17988kb
input:
1000 595091201 939900592 655807790 642715685 911814092 498974048 87484977 605627947 65970121 215254010 786130847 155272420 993721611 607769332 698217409 881103787 844746003 87889791 401779231 584665609 65065703 736064488 562406345 576928316 17010891 977424575 177416710 646960699 907121804 710916955 ...
output:
34
result:
ok single line: '34'
Test #29:
score: 36
Accepted
time: 2ms
memory: 17984kb
input:
1000 948100279 395555599 14777183 9199934 304230494 715632610 9217162 14759955 310142435 721544551 865212185 745675748 9394061 14583056 865212185 784874973 865212185 906796364 865212185 31989188 865212185 480628279 865212185 964360884 865212185 340642141 20210436 3766681 23931134 45983 865212185 291...
output:
14
result:
ok single line: '14'
Test #30:
score: 36
Accepted
time: 2ms
memory: 17900kb
input:
1000 594985039 625511711 994879266 920449505 389314115 419840787 472340604 502867279 30116006 60642677 662107628 692634303 365090885 395617555 408532654 439059330 357063799 387590470 67129230 97655909 609060722 639587399 23014154 53540828 396833235 427359905 357198921 387725591 232892405 263419076 3...
output:
10
result:
ok single line: '10'
Test #31:
score: 36
Accepted
time: 0ms
memory: 18000kb
input:
1000 356940579 851476671 397464277 845802253 124390155 791067082 12013794 794223318 714298701 936067123 459558840 830422395 477536615 842833187 953972866 696392954 431850846 858130385 742405622 907960208 73726026 782573942 157477949 824154869 439413217 850568015 253214134 919891060 676339143 9740266...
output:
43
result:
ok single line: '43'
Subtask #4:
score: 31
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #32:
score: 31
Accepted
time: 220ms
memory: 36212kb
input:
331723 666751776 455550721 417970264 87986159 521744278 25774674 304608665 188134996 423947789 229236315 287498390 481299932 874554097 838912682 597479256 761671921 476061839 671216682 978453002 970303497 407939338 905778253 28517467 775347134 584938460 905752120 965051134 165301290 105201049 248758...
output:
519
result:
ok single line: '519'
Test #33:
score: 31
Accepted
time: 274ms
memory: 39340kb
input:
423339 143544876 255567697 758660655 604284811 583461932 814644295 273070559 255687648 425423426 660898573 642919027 365039157 471977253 711641142 278349049 814223271 412488757 344959351 568268915 798647677 110969383 467735793 257172855 11016834 557877283 343199941 563886698 637896394 852658986 6920...
output:
553
result:
ok single line: '553'
Test #34:
score: 31
Accepted
time: 324ms
memory: 41292kb
input:
500000 904996560 802335709 971741625 138273196 421543586 711132989 425079808 229596781 517684175 848637127 490078544 741025444 877245128 413805177 57916854 28311525 13899421 731187886 265039863 993276097 885346461 684282393 707307141 575855532 558855311 131723566 330179550 593370367 45769504 6783597...
output:
615
result:
ok single line: '615'
Test #35:
score: 31
Accepted
time: 267ms
memory: 42104kb
input:
500000 134889 194619 492903 221770 55598 167701 476604 142203 297564 420406 142145 234307 38489 222386 211206 474994 12561 187469 267588 498835 127430 221853 323316 397368 74362 370152 17522 201439 286694 281049 149800 245334 426900 298192 263025 237567 115105 141739 17271 384282 388679 441532 46133...
output:
629
result:
ok single line: '629'
Test #36:
score: 31
Accepted
time: 332ms
memory: 42324kb
input:
500000 528577454 874037549 695516427 455748060 63730632 733146309 720504153 716327092 670941640 746015718 16964511 804420980 90168023 448474963 540475230 553615296 15247233 663121094 725122426 389948300 714048686 319366433 413840525 636964339 957049241 799814285 824576601 742623461 721978332 1198789...
output:
829
result:
ok single line: '829'
Test #37:
score: 31
Accepted
time: 336ms
memory: 42188kb
input:
500000 910533650 690866096 546762325 199565753 929234058 260754663 341662449 349185444 241979388 150031512 989700908 34114166 886809904 892422053 310441801 20476514 56515531 437312970 934880297 145751248 63081686 798052043 384048539 716652891 320215412 884797757 80196350 163785886 805924479 90111083...
output:
587
result:
ok single line: '587'
Test #38:
score: 31
Accepted
time: 320ms
memory: 42180kb
input:
500000 371048964 985185229 173895798 107271394 378838771 977395422 722532913 145372414 867840754 290680255 173895798 650465578 173895798 622133174 173895798 734260886 963795555 392438638 808523785 547710408 686138303 50688480 173895798 916262283 299658056 787305847 173895798 156144488 534406933 5966...
output:
307
result:
ok single line: '307'
Test #39:
score: 31
Accepted
time: 494ms
memory: 43628kb
input:
500000 283677246 27077636 390267666 133668052 186810647 5 761375404 292759837 962212830 91922410 154726541 4 191901766 10 368582928 111983313 363075345 106475729 80070432 2 139394082 5 994313743 59821496 837175722 216959521 328555315 71955702 893289115 160846125 548971699 292372082 811483071 2426521...
output:
128493
result:
ok single line: '128493'
Test #40:
score: 31
Accepted
time: 305ms
memory: 43648kb
input:
500000 216609125 845324545 744653890 708958672 561452555 892160002 800957225 652655340 48564269 932051425 430724147 945989634 13670354 897157518 386518378 901783860 909878931 543733631 746063309 707549257 377764453 893029943 517005357 936607200 992865874 460746692 825737476 627875086 115971865 94596...
output:
24
result:
ok single line: '24'
Test #41:
score: 31
Accepted
time: 973ms
memory: 42392kb
input:
500000 931585991 1 757408402 1 850472346 1 392473110 1 832908007 1 519878068 1 509547744 1 71130365 1 853161339 1 356730798 1 748636254 1 168914203 1 276105464 1 70380352 1 255622752 1 675004407 1 155240434 1 917854752 1 203837663 1 921869244 1 335076893 1 662191938 1 156363076 1 772054258 1 9616483...
output:
499870
result:
ok single line: '499870'
Extra Test:
score: 0
Extra Test Passed