QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562923 | #3944. Alehouse | WeaRD276 | AC ✓ | 153ms | 16380kb | C++20 | 2.2kb | 2024-09-13 23:01:22 | 2024-09-13 23:01:22 |
Judging History
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'