QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#782900#5513. Advertisement 2_lax100 ✓987ms43648kbC++201.8kb2024-11-25 22:04:332024-11-25 22:04:33

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 22:04:33]
  • 评测
  • 测评结果:100
  • 用时:987ms
  • 内存:43648kb
  • [2024-11-25 22:04:33]
  • 提交

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