QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562923#3944. AlehouseWeaRD276AC ✓153ms16380kbC++202.2kb2024-09-13 23:01:222024-09-13 23:01:22

Judging History

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

  • [2024-09-13 23:01:22]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:16380kb
  • [2024-09-13 23:01:22]
  • 提交

answer

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

#include  <ext/pb_ds/assoc_container.hpp>
#include  <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<long long, long long> pll;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<long long, long long> > vpll;
typedef set<int> si;
typedef set<long long> sll;
typedef map<int, int> mii;
typedef map<long long, long long> mll;

#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

constexpr int INF = 1e9 + 47;
constexpr long long LINF = (ll) 1e18 + 4747;
constexpr int MOD = 998244353;
constexpr int N = 1e5 + 47;

int solve()
{
	int n;
	ll k;
	if (!(cin >> n >> k))
		return 1;
	
	multiset<pair<ll, bool>> events;
	FOR (i, 0, n)
	{
		int x, y;
		cin >> x >> y;
		events.insert(MP(x, false));
		events.insert(MP(y + k, true));
	}
		
	int ans = 0;
	int cnt = 0;
	for (auto it = events.begin(); it != events.end(); it++)
	{
		if ((*it).S)
			--cnt;
		else
			++cnt;
		ans = max(ans, cnt);
	}
	cout << ans << '\n';
	return 0;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3544kb

input:

6 2
0 2
1 8
5 9
2 4
7 8
10 10

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

10 1
7 31
28 30
0 28
13 24
27 38
1 24
8 36
6 31
4 16
14 17

output:

8

result:

ok single line: '8'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 2
28 32
25 32
5 23
2 37
10 27
16 38
10 19
23 34
3 5
13 38

output:

7

result:

ok single line: '7'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10 4
30 35
15 37
30 34
12 14
4 38
8 34
0 30
30 37
23 38
16 35

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10 5
6 25
17 23
33 34
6 11
9 30
18 35
3 14
15 19
4 5
1 25

output:

7

result:

ok single line: '7'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

10 1
10 11
29 30
18 22
0 1
32 33
36 39
3 7
16 17
26 27
12 15

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10 2
8 9
23 24
36 37
31 34
0 2
25 30
17 21
15 16
10 13
5 6

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

10 3
9 13
36 37
6 7
33 34
16 17
20 23
29 32
3 4
1 2
25 26

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

10 6
23 24
16 20
8 12
31 35
5 6
36 37
0 2
25 27
14 15
38 39

output:

3

result:

ok single line: '3'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 10
11 12
14 17
28 29
37 39
19 21
0 1
2 5
31 32
8 10
22 23

output:

4

result:

ok single line: '4'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 20
29 30
0 1
2 5
15 16
31 36
37 38
11 13
17 20
7 10
25 27

output:

6

result:

ok single line: '6'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

10 30
12 14
38 39
9 11
4 5
17 19
32 35
20 25
30 31
28 29
2 3

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

10 40
21 22
19 20
36 37
0 7
25 28
38 39
8 9
23 24
30 33
14 17

output:

10

result:

ok single line: '10'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10 1
11 12
11 12
14 15
8 9
4 5
18 19
34 35
16 17
9 10
14 15

output:

3

result:

ok single line: '3'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

10 2
6 8
17 19
18 20
16 18
19 21
28 30
15 17
33 35
29 31
4 6

output:

5

result:

ok single line: '5'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

10 3
13 16
1 4
9 12
10 13
33 36
3 6
23 26
15 18
0 3
2 5

output:

4

result:

ok single line: '4'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10 4
0 4
26 30
26 30
30 34
14 18
28 32
30 34
23 27
16 20
18 22

output:

6

result:

ok single line: '6'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 5
26 31
11 16
33 38
1 6
17 22
18 23
19 24
7 12
34 39
23 28

output:

5

result:

ok single line: '5'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 6
31 37
11 17
21 27
12 18
11 17
28 34
7 13
30 36
31 37
15 21

output:

5

result:

ok single line: '5'

Test #20:

score: 0
Accepted
time: 153ms
memory: 16092kb

input:

100000 1
479491731 593155801
120474795 295164977
167553582 203123863
132068717 257673502
44134863 305392420
79021782 96847464
61585901 64805694
173968060 450095163
45813626 571891514
117405246 553779931
75422364 232003883
158531998 483695480
225467311 301625203
68411477 304808240
155378194 532336078...

output:

50346

result:

ok single line: '50346'

Test #21:

score: 0
Accepted
time: 135ms
memory: 16140kb

input:

99999 1
261819666 277720690
99990456 113457878
567704588 568260340
42313949 221633081
196419730 504730910
525399518 568072203
86814781 109378611
233634262 267637710
119474410 552753295
20178329 482705002
167781447 219886133
521735609 546198020
90557931 575961811
129570929 151793145
96665500 36112621...

output:

50223

result:

ok single line: '50223'

Test #22:

score: 0
Accepted
time: 138ms
memory: 16116kb

input:

100000 6047999
66890246 132540497
395518528 540131062
64622663 100406252
412341121 435064178
254194547 426812700
180487696 566295577
294240359 462312304
289914057 411212348
49130006 330398698
289460992 331928482
184354042 554521019
316618069 417051120
482641814 487147835
76820876 453438186
170318111...

output:

51126

result:

ok single line: '51126'

Test #23:

score: 0
Accepted
time: 142ms
memory: 16092kb

input:

99999 6047999
291687541 401845798
106679819 507674416
37364355 134956632
410765686 528595359
140405876 184626442
307713784 417542540
67036699 395754919
99825615 224260322
96563142 371263249
121645884 316945221
328621305 472158505
93419693 536810611
63962845 166171031
279073014 294778946
271639068 38...

output:

50920

result:

ok single line: '50920'

Test #24:

score: 0
Accepted
time: 146ms
memory: 16116kb

input:

99999 604799999
377181766 407872700
269943895 552908825
328431941 584189912
93871936 97559337
291135283 529188054
52713049 490559525
215779017 383526901
332184964 353093068
133882092 450576452
558983073 604618237
224691403 395506311
144204726 346799099
214525532 543445904
34905891 398591359
10111626...

output:

99999

result:

ok single line: '99999'

Test #25:

score: 0
Accepted
time: 109ms
memory: 16096kb

input:

100000 1
65156635 65161852
487890087 487890886
397538760 397548369
366176033 366180578
462528689 462530156
179779029 179780231
432403821 432404700
41813045 41818051
481560761 481562301
495147057 495149262
213281300 213282143
391680957 391681190
397583932 397586730
83487693 83489224
518446617 5184509...

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 131ms
memory: 16048kb

input:

100000 6047999
350078413 350082273
481544300 481547841
73084131 73088348
121127153 121131836
431135483 431138776
362145326 362147399
578871506 578872676
432822765 432832408
193890629 193892936
304134195 304134259
303089844 303094139
447070155 447071656
35059878 35060008
603880836 603883051
393719492...

output:

1089

result:

ok single line: '1089'

Test #27:

score: 0
Accepted
time: 103ms
memory: 16348kb

input:

99999 6047
309658150 309660829
221449460 221452959
462770228 462773033
44654986 44658205
502384099 502388471
138578029 138579715
104245368 104257938
423899371 423903737
257482654 257483134
477300820 477314874
17869901 17871372
293736787 293737042
110131504 110137566
201552787 201553781
551015608 551...

output:

7

result:

ok single line: '7'

Test #28:

score: 0
Accepted
time: 110ms
memory: 16152kb

input:

100000 1
417424808 417424809
577242267 577242268
477156479 477156480
339037518 339037519
577450816 577450817
468447995 468447996
257162238 257162239
420080965 420080966
579371609 579371610
130338740 130338741
465344728 465344729
588458866 588458867
41057224 41057225
168349516 168349517
585937276 585...

output:

2

result:

ok single line: '2'

Test #29:

score: 0
Accepted
time: 103ms
memory: 16344kb

input:

99999 1
254075665 254075666
189587450 189587451
544894135 544894136
289704680 289704681
249506557 249506558
82823200 82823201
250780084 250780085
227661308 227661309
142514185 142514186
296808077 296808078
432322165 432322166
430514830 430514831
162752013 162752014
465991187 465991188
537253454 5372...

output:

2

result:

ok single line: '2'

Test #30:

score: 0
Accepted
time: 113ms
memory: 16220kb

input:

100000 6047
258967580 258973627
255269990 255276037
197618176 197624223
266092494 266098541
149006509 149012556
393045477 393051524
599321116 599327163
20483865 20489912
434548937 434554984
359310026 359316073
35684704 35690751
127235599 127241646
245387010 245393057
578426567 578432614
539824291 53...

output:

11

result:

ok single line: '11'

Test #31:

score: 0
Accepted
time: 134ms
memory: 16204kb

input:

99999 60479
348166208 348226687
220793845 220854324
279273892 279334371
486229471 486289950
224037134 224097613
567019632 567080111
441237870 441298349
358776437 358836916
481796032 481856511
219402411 219462890
434169350 434229829
505553592 505614071
343554187 343614666
364796043 364856522
41592087...

output:

40

result:

ok single line: '40'

Test #32:

score: 0
Accepted
time: 136ms
memory: 16144kb

input:

99999 60479999
419986612 480466611
338949345 399429344
54442574 114922573
110655182 171135181
485255814 545735813
476987387 537467386
223371205 283851204
339129750 399609749
81102822 141582821
114563226 175043225
314937353 375417352
318887687 379367686
48891272 109371271
415792038 476272037
47253353...

output:

22487

result:

ok single line: '22487'

Test #33:

score: 0
Accepted
time: 108ms
memory: 16216kb

input:

100000 1
552499023 552499993
65568561 65571797
100583497 100586808
290872457 290874022
377780254 377781508
379416612 379418131
19836370 19837089
258737292 258740972
75390907 75392219
547562905 547567808
205232631 205234715
329732475 329734342
298196333 298196849
369227183 369227946
174318616 1743227...

output:

18

result:

ok single line: '18'

Test #34:

score: 0
Accepted
time: 106ms
memory: 16308kb

input:

100000 1
471043489 471047156
203028351 203029443
250898020 250900472
576078154 576080162
499223134 499227207
435594295 435597048
101166647 101167953
434230364 434235191
314798127 314798869
466881008 466889362
78967148 78970889
260310492 260313668
342704364 342707061
11117889 11118966
299356174 29935...

output:

17

result:

ok single line: '17'

Test #35:

score: 0
Accepted
time: 97ms
memory: 16376kb

input:

100000 1
66330286 66333662
80103186 80117292
528773041 528775804
237552925 237554118
508349809 508351965
11905095 11906916
461274213 461283863
393492647 393498745
363133700 363133816
591994561 591994888
297727931 297730540
383082880 383084569
36207455 36210100
76794400 76794488
479283804 479287451
4...

output:

17

result:

ok single line: '17'

Test #36:

score: 0
Accepted
time: 112ms
memory: 16148kb

input:

100000 10000
434973998 434974032
481427067 481427658
449853847 449855104
528064658 528065517
337102422 337105820
324489470 324499856
199836305 199836424
408646428 408647408
430011230 430011319
324305736 324307702
363192521 363203251
569462246 569462644
19548836 19549130
168394662 168398613
486752180...

output:

20

result:

ok single line: '20'

Test #37:

score: 0
Accepted
time: 110ms
memory: 16380kb

input:

99999 1
232839691 232840891
282990714 282995347
571018731 571023287
33878925 33892240
109829743 109831955
443604079 443605069
464106165 464113713
29040046 29041161
539873089 539877379
434056993 434059718
425389158 425389348
155315871 155319416
113865498 113868712
411754276 411759579
288488348 288488...

output:

18

result:

ok single line: '18'

Test #38:

score: 0
Accepted
time: 104ms
memory: 16100kb

input:

99999 1
275129675 275130141
270898417 270899251
534930859 534935981
197107125 197107154
378587856 378588049
13227781 13238405
446533783 446536612
277737912 277741453
397942898 397943638
305205798 305213084
532284451 532285955
432265725 432266909
447135146 447137838
259173899 259176766
412789034 4127...

output:

18

result:

ok single line: '18'

Test #39:

score: 0
Accepted
time: 99ms
memory: 16148kb

input:

99999 1
77973246 77973379
493375825 493377426
234551559 234551797
222194461 222200266
486730941 486737831
51591246 51591766
453884946 453884955
98579591 98585320
543158760 543163521
592106185 592109819
342786706 342788290
402807640 402810503
123082324 123082535
298104774 298105270
172962306 17296919...

output:

17

result:

ok single line: '17'

Test #40:

score: 0
Accepted
time: 115ms
memory: 16148kb

input:

99999 10000
284812026 284813598
263899966 263900885
286169232 286169272
280244254 280246080
367084013 367084223
593095306 593095377
571813465 571818567
604793567 604793832
144189052 144189720
600169322 600169853
56190661 56193965
105904905 105906425
242350405 242354026
534672683 534674378
535600451 ...

output:

20

result:

ok single line: '20'