QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791901#5513. Advertisement 2vinaka33 368ms24856kbC++141.3kb2024-11-28 21:50:242024-11-28 21:50:47

Judging History

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

  • [2024-11-28 21:50:47]
  • 评测
  • 测评结果:33
  • 用时:368ms
  • 内存:24856kb
  • [2024-11-28 21:50:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

signed main() {
  for(string s: {NAME, ""}) {
    if (fopen((s + ".inp").c_str(), "r")) {
      freopen((s + ".inp").c_str(), "r", stdin);
      freopen((s + ".out").c_str(), "w", stdout);
      break;
    }
  }
  cin.tie(0)->sync_with_stdio(0);

  int n;
  cin >> n;

  set < pii > s;

  FOR(i, 1, n) {
    int X, E;
    cin >> X >> E;

    int l = X - E, r = X + E;

    set < pii > :: iterator it = s.lower_bound({l, 0});
    while (it != s.end()) {
      if (it -> se > r) {
        break;
      }

      it = next(it);
      s.erase(prev(it));
    }

    it = s.upper_bound({l, (int)1e9 + 1});
    if (it == s.begin() || prev(it) -> se < r) {
      s.insert({l, r});
    }

//    for (auto x: s) {
//      cout << x.fi << " " << x.se << "\n";
//    }
//    cout << "\n";
  }

  cout << sz(s);

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 77ms
memory: 9088kb

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: 102ms
memory: 7232kb

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: 185ms
memory: 3752kb

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: 45ms
memory: 3532kb

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: 368ms
memory: 24856kb

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: 345ms
memory: 13748kb

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: 196ms
memory: 3812kb

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: 70ms
memory: 3784kb

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: 3544kb

input:

3
231636235 354089104
228392707 930073348
587735804 575683740

output:

2

result:

ok single line: '2'

Test #10:

score: 23
Accepted
time: 0ms
memory: 3524kb

input:

2
44803615 325394921
960290812 913042209

output:

2

result:

ok single line: '2'

Test #11:

score: 23
Accepted
time: 0ms
memory: 3748kb

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: 3528kb

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: 0ms
memory: 3596kb

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: 0ms
memory: 3480kb

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: 0ms
memory: 3480kb

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: 3828kb

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: 3548kb

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: 0ms
memory: 3548kb

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: 0ms
memory: 3776kb

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: 3812kb

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: 0ms
memory: 3480kb

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: 0ms
memory: 3748kb

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: 0ms
memory: 3612kb

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: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #24:

score: 36
Accepted
time: 1ms
memory: 3424kb

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: 1ms
memory: 3600kb

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: 1ms
memory: 3532kb

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: 1ms
memory: 3588kb

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: 0
Wrong Answer
time: 1ms
memory: 3528kb

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:

37

result:

wrong answer 1st lines differ - expected: '34', found: '37'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%