CT30411

The Busy Hall at Rootwater

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Marek the inventory keeper watches over the mangrove channels of Rootwater's stores of segments. A careful computation stands between order and chaos. Task: n crews each guard a half-open interval [s,e). An interval ending at time t does not overlap one starting at t. Print the maximum number overlapping at any instant. Input format: First line: n. Next n lines: s e. Output format: Print the maximum simultaneous overlap. Constraints: 1 <= n <= 2342; 0 <= s < e <= 10^9.

Example 1:

Input: 397 903408738 903408741 941192489 941192514 178617468 178617469 647724136 647724150 871286877 871286882 569936485 569936560 176410936 176410989 181382693 181382740 890412267 890412350 258234915 258234934 144822409 144822446 764014273 764014357 575244343 575244389 703248941 703249016 69789096 69789104 936373970 936374040 132259471 132259516 512430608 512430640 749154529 749154537 720379629 720379721 80739481 80739504 487798168 487798194 518799926 518799954 563345472 563345514 960276261 960276269 780960894 780960985 849843938 849844011 566060373 566060440 4018068 4018152 281555700 281555753 729611027 729611064 775854488 775854582 833001435 833001466 5791157 5791173 646451756 646451763 589711236 589711286 346749156 346749253 101664757 101664831 173426751 173426782 332160094 332160138 804340068 804340149 794218743 794218786 598331702 598331798 185146318 185146363 917213685 917213697 322704550 322704585 823365280 823365328 4824115 4824123 671971700 671971787 84064967 84064972 249112950 249113026 406585357 406585451 74029593 74029655 69849146 69849175 312306408 312306419 27036228 27036282 327852325 327852369 694466920 694466928 831837699 831837796 825077799 825077853 987524115 987524127 804504802 804504821 779652117 779652150 512180243 512180260 531759434 531759458 732105313 732105355 877072790 877072874 99243297 99243303 401104781 401104783 669748307 669748402 471147464 471147551 747207388 747207476 492831661 492831682 739303795 739303890 301051744 301051775 858264850 858264918 944948313 944948364 928262203 928262243 302921995 302922032 571622593 571622617 198319342 198319366 839541069 839541130 125279755 125279781 632201912 632201928 145221230 145221292 467712890 467712976 381436079 381436154 865746338 865746379 720187377 720187378 445543804 445543817 17393958 17394031 848794205 848794234 999457303 999457321 791651749 791651839 485583211 485583263 478918104 478918150 682429837 682429855 132208840 132208908 33489725 33489794 788014999 788015046 943940761 943940825 846485708 846485804 995934391 995934464 11833508 11833544 589837265 589837268 641186023 641186077 682892762 682892817 110924475 110924507 272052047 272052115 210935882 210935915 434013266 434013358 589432617 589432680 584095358 584095403 400014163 400014232 768942535 768942584 665754197 665754201 87610584 87610631 892581794 892581818 794082627 794082685 434130101 434130189 891388850 891388851 942649315 942649344 943584092 943584103 571545358 571545409 461147499 461147573 312780903 312780930 16568636 16568728 639015874 639015956 935387142 935387187 675458716 675458747 398305659 398305734 497843547 497843560 984832488 984832531 975510138 975510146 197244750 197244792 152714661 152714759 703781506 703781576 746253300 746253392 207284388 207284421 588979259 588979349 890001003 890001088 135317615 135317635 897984198 897984231 865764906 865764934 377468750 377468754 582544575 582544591 765779026 765779058 654020949 654021027 940391751 940391847 136020999 136021010 895900127 895900222 122953337 122953399 760499117 760499150 762815587 762815645 20042874 20042943 65226621 65226712 79956882 79956945 762214172 762214226 279267677 279267768 146643752 146643799 273138635 273138681 480671237 480671272 236972374 236972420 806037555 806037567 680629712 680629761 614974310 614974371 723211083 723211104 319811796 319811838 992465769 992465821 838090506 838090598 514730985 514731038 632632801 632632849 287231635 287231656 898520192 898520269 773887016 773887032 46230781 46230875 346544260 346544275 607917423 607917475 558751661 558751749 28899930 28900029 190941228 190941287 761537351 761537438 44886725 44886780 789782073 789782100 865181256 865181336 832834074 832834098 635890419 635890506 89410377 89410471 770403389 770403479 474997746 474997807 595962702 595962778 628198398 628198494 953307180 953307219 389960820 389960847 81027579 81027606 80551142 80551214 448079060 448079100 359123666 359123743 845854429 845854525 737901588 737901665 98595494 98595500 559633082 559633092 246597764 246597765 34356195 34356214 485974297 485974372 335737826 335737859 595949953 595949974 410190417 410190491 432701737 432701779 401720525 401720610 23366360 23366453 40419483 40419575 539659779 539659848 511234534 511234583 256414006 256414065 52099624 52099705 871903502 871903554 723044266 723044278 782316294 782316348 418062128 418062192 122262397 122262492 848407300 848407396 788152015 788152025 626640041 626640103 265001262 265001340 321582412 321582483 776222516 776222519 242531936 242532029 661479862 661479916 661805627 661805717 649325068 649325152 864080316 864080375 879447599 879447609 29202040 29202139 396196860 396196926 133609541 133609550 912619528 912619594 5008412 5008500 959886984 959887063 999203722 999203727 912069379 912069472 52888617 52888649 193662120 193662123 975050883 975050950 15106951 15106976 763756552 763756607 166441855 166441933 823456414 823456481 526962655 526962680 57501194 57501287 549712852 549712950 784183189 784183233 705089152 705089204 733062247 733062313 45434767 45434788 117378676 117378775 710595724 710595788 690781436 690781468 111208826 111208886 714927962 714928017 485803739 485803753 423018163 423018260 269412794 269412803 921605338 921605374 666773941 666773957 149855941 149856015 663420166 663420180 674800436 674800500 214898623 214898629 474191064 474191073 586314956 586315053 894284244 894284331 536076481 536076562 908835099 908835157 846619344 846619355 902668643 902668694 981486860 981486865 882024043 882024060 595365145 595365189 624479399 624479416 318095530 318095597 119692899 119692914 247209997 247210066 480753498 480753584 486465871 486465934 563489237 563489263 834950955 834951032 566916966 566917000 630084155 630084167 462166479 462166543 893716173 893716209 757227280 757227313 657405275 657405342 342150741 342150742 749142801 749142879 143174348 143174398 162049768 162049809 551628302 551628364 890598122 890598176 557273658 557273748 701162384 701162411 17368015 17368103 582758637 582758710 116583013 116583070 370147997 370148051 140183229 140183235 66692630 66692699 510933291 510933303 431826997 431827056 29548023 29548100 364736280 364736345 493478716 493478728 295507299 295507359 415124318 415124328 795786380 795786409 691426980 691426994 347890694 347890728 701785627 701785678 737330662 737330709 105285982 105286051 940639941 940639951 846472739 846472790 391301748 391301753 745659265 745659362 847097335 847097405 63553992 63554050 795888712 795888713 491809749 491809826 982527246 982527344 362334323 362334371 124211256 124211276 567298114 567298136 25231103 25231110 792604655 792604734 830154210 830154289 148609308 148609362 798321246 798321329 709690127 709690141 971246020 971246093 595891608 595891707 269878803 269878807 763769940 763769968 890937043 890937138 672584125 672584201 203799863 203799929 963150796 963150799 456065663 456065685 993093740 993093837 657886566 657886609 277254158 277254177 506658502 506658601 386486985 386487018 698898425 698898494 443126129 443126222 903498672 903498688 938657256 938657295 60384164 60384251 112335154 112335155 61883869 61883940 382200639 382200697 836771901 836771941 519307609 519307633 619943752 619943839 798608662 798608670 551398255 551398317 286669620 286669660 206252489 206252556 4943541 4943625 953099913 953099923 673986637 673986690 100694943 100694961 974428171 974428229 456616026 456616040 888393840 888393914 575393697 575393743 240547286 240547364 7447758 7447804 559960036 559960045 407366253 407366320 231545794 231545891 872467726 872467815 507502914 507502922 761706478 761706533 597068465 597068538 252461905 252462001 502800492 502800591 961867912 961867925 483113353 483113434 774233391 774233400 19607053 19607146 585599511 585599542 93534869 93534901 17486606 17486614 751917721 751917782 895061824 895061894 810637378 810637456 952893657 952893718
Output: 1

Example 2:

Input: 439 173795944 173795999 800864566 800864584 460442063 460442162 195862995 195863092 572329205 572329230 334904163 334904200 617279705 617279790 288822136 288822151 879124994 879125056 623993558 623993657 255097732 255097805 592125182 592125213 965272605 965272696 57050908 57050913 486154032 486154083 413743313 413743347 839290957 839291002 274000776 274000869 795820112 795820167 594171540 594171543 10252786 10252796 900361397 900361493 211744320 211744391 894828230 894828264 624593494 624593514 435199115 435199193 361352221 361352291 540337203 540337218 513329016 513329048 100996256 100996300 524690548 524690639 564572193 564572213 379009039 379009097 113327972 113328003 780586205 780586207 5365330 5365370 687803338 687803349 462053752 462053828 98037843 98037881 522762707 522762717 983489881 983489903 170496969 170496983 442991047 442991116 476514948 476514959 547319094 547319164 679796847 679796882 82748027 82748051 32601943 32601989 173801970 173801981 57247799 57247847 629887457 629887535 847879232 847879242 53417586 53417642 542533174 542533206 467827056 467827069 478294725 478294785 625072167 625072205 168072663 168072746 498703597 498703618 246915074 246915117 165999583 165999589 697278115 697278178 577979113 577979137 247937546 247937594 999784322 999784419 939189923 939189967 975754821 975754900 361807357 361807400 764022982 764023038 179748409 179748461 358862877 358862898 223246900 223246986 212682011 212682085 592707623 592707629 464549806 464549872 662483780 662483809 210275140 210275216 616008759 616008779 529477437 529477451 874902768 874902814 675068976 675069058 339752978 339752989 517196873 517196953 308172391 308172481 122220394 122220474 575283566 575283594 561441073 561441079 203251502 203251592 859208737 859208751 862144779 862144789 959566589 959566634 700545015 700545088 697492072 697492105 123451765 123451812 148345637 148345703 578040445 578040545 25911901 25911925 758240453 758240529 595041554 595041634 646381656 646381743 728023083 728023142 334384932 334384989 733508264 733508356 758798580 758798593 516707575 516707628 393474684 393474718 506297283 506297288 834265251 834265298 830951384 830951418 963505636 963505641 656902640 656902691 826154151 826154160 195822639 195822650 542160004 542160065 910345144 910345182 475725679 475725742 701529287 701529333 353826223 353826310 967916931 967917023 861042485 861042499 588158149 588158219 183028948 183029044 964264512 964264567 600734907 600734991 918394585 918394598 338332684 338332741 741850099 741850159 245428356 245428408 570534169 570534200 358897399 358897483 826241943 826241949 255008180 255008270 987738169 987738212 283929743 283929842 489274145 489274164 999996943 999996947 855481886 855481949 799939505 799939587 796607777 796607870 275248710 275248745 171912053 171912065 992190644 992190723 60056325 60056390 6772519 6772527 713244604 713244658 909561223 909561266 319828867 319828904 173101332 173101389 272423696 272423698 417784876 417784963 718778524 718778619 103600868 103600890 718084361 718084459 573955269 573955282 314294454 314294530 588073045 588073140 4253261 4253279 55254251 55254276 553397257 553397280 804851127 804851206 112723118 112723120 678054109 678054111 594926415 594926450 253691729 253691731 753093023 753093033 882966447 882966458 800456619 800456686 382933730 382933790 514774976 514775016 87450863 87450941 875621437 875621454 421832762 421832773 102948449 102948477 909094590 909094634 853233534 853233586 348868742 348868759 706066215 706066232 229165410 229165478 38421869 38421914 243828870 243828944 697344493 697344540 863984171 863984267 29071187 29071250 262083337 262083340 138355710 138355723 447881500 447881551 714446258 714446310 472176747 472176831 925461666 925461674 51368589 51368651 243892767 243892862 456932853 456932862 113686644 113686731 30774394 30774433 816871558 816871566 19853111 19853156 740002947 740003019 458733234 458733324 955531736 955531782 26416990 26417018 188739922 188739992 76394083 76394129 280614252 280614270 163284174 163284225 622506854 622506898 350513984 350514049 718647546 718647581 355508212 355508264 714941246 714941341 826040848 826040908 168719938 168720009 536876119 536876197 240456888 240456900 487196839 487196869 688712530 688712556 196157196 196157266 102866940 102867009 299975121 299975125 916256748 916256798 566406435 566406443 446837971 446838010 475095799 475095804 643807546 643807586 657891851 657891875 12579386 12579466 419534607 419534612 99667665 99667701 964711248 964711278 635477649 635477667 921165353 921165410 161768015 161768103 826181775 826181815 611587310 611587334 111360409 111360467 36514113 36514128 4010586 4010589 184830804 184830896 994814180 994814244 432409557 432409643 854607626 854607636 856045251 856045335 495365517 495365521 254885745 254885828 21993676 21993683 156049770 156049816 215195184 215195193 924952571 924952627 108361791 108361890 152682521 152682570 818076769 818076799 751818520 751818570 762985317 762985343 180256597 180256657 926448542 926448625 358013686 358013728 940244916 940244950 809415903 809415995 283687412 283687496 196603661 196603674 274217381 274217451 293086177 293086192 818304468 818304552 455326315 455326381 107129886 107129927 776014422 776014491 40487412 40487420 519150415 519150458 741872444 741872478 654540520 654540608 333336502 333336523 54238160 54238243 424455027 424455104 779734604 779734645 265708095 265708122 46654934 46654969 535006932 535007004 216446182 216446199 454498165 454498191 504547315 504547318 494970615 494970705 539534538 539534602 452515704 452515787 15048025 15048119 629881975 629882075 725769055 725769095 869886882 869886959 396382476 396382498 839591568 839591658 162778743 162778782 178650207 178650223 851427666 851427686 280521835 280521854 166935329 166935402 527134728 527134789 239508727 239508754 933188933 933188997 670695483 670695559 296602135 296602181 674860753 674860777 285265214 285265236 527475342 527475388 504020804 504020876 207328639 207328653 433838796 433838829 897921917 897921943 576490178 576490254 510202988 510203012 291403863 291403876 157871257 157871348 771410185 771410228 422722907 422722990 488264772 488264797 837170897 837170992 786635234 786635286 971612552 971612628 997235314 997235394 338233077 338233115 875893386 875893433 416822166 416822244 727201509 727201550 10222377 10222461 190545007 190545013 922334507 922334532 119523589 119523591 192061083 192061118 977007402 977007494 154505226 154505289 205592317 205592405 771873720 771873805 328550817 328550905 694902433 694902518 394245656 394245680 343745464 343745485 824605636 824605702 473323424 473323467 3405020 3405068 880385846 880385867 300022094 300022105 312327409 312327500 203178026 203178044 603445418 603445467 192840370 192840453 958242376 958242445 987937322 987937405 457536006 457536087 681562997 681563073 523265380 523265393 114192462 114192507 664269877 664269931 342074905 342074961 250248365 250248419 967956995 967957091 857311486 857311579 848111022 848111048 537373647 537373724 440040213 440040283 864521240 864521332 200740072 200740162 291268496 291268525 448116417 448116454 107501658 107501706 717849521 717849526 684936767 684936786 367010050 367010112 50862793 50862820 845814701 845814745 537089405 537089435 325334501 325334545 383057822 383057905 79556004 79556007 690421757 690421849 418546453 418546477 154442135 154442188 641932084 641932115 392835854 392835936 70958042 70958057 32000908 32000935 161677467 161677504 187951881 187951904 414034211 414034213 740297483 740297540 290804115 290804170 792773330 792773404 56334406 56334418 2316217 2316305 63959602 63959664 281707055 281707102 998503111 998503165 100264228 100264303 506236008 506236021 979984546 979984562 605896571 605896662 522868748 522868842 40644093 40644135 887800422 887800509 340663123 340663129 91659830 91659862 576176724 576176797 924288127 924288219 469705274 469705349 472982109 472982187 190949853 190949900 318779643 318779714 703036666 703036735 276603541 276603583 946277102 946277138 277667442 277667519 928449033 928449093 478019595 478019605 913575996 913576070 201305378 201305475 402476964 402477020 106002417 106002477 416802796 416802880 955276452 955276530 208093008 208093101 763443749 763443817 439953398 439953415 336099233 336099238 935604427 935604510 190262859 190262877 430630666 430630694 654975600 654975697 47629711 47629719 298144979 298145027 606187087 606187097 942331958 942331976 910870466 910870540 277974410 277974510 398172885 398172890 538088777 538088827 767320980 767321046 49306313 49306398 284928460 284928492 541737857 541737881 55357294 55357300 957584548 957584634 413683559 413683638 436184153 436184226
Output: 1

Example 3:

Input: 132 916465636 916465731 976646717 976646769 58536477 58536498 39365084 39365132 635604565 635604584 804457561 804457599 557581622 557581719 437198661 437198673 756075434 756075518 935408226 935408299 659650733 659650811 494182433 494182472 628830892 628830987 680054739 680054750 284492698 284492726 856001585 856001642 660149039 660149066 743808692 743808743 280843041 280843120 725767515 725767553 639098440 639098538 83583131 83583153 740720732 740720785 952209092 952209173 542594874 542594911 255349721 255349811 336833986 336833994 578583689 578583784 938994780 938994861 384734763 384734840 249130942 249130943 831631696 831631748 112004217 112004243 237802402 237802434 150860689 150860690 44063700 44063720 617466530 617466555 500434091 500434094 562690594 562690669 668428805 668428809 989059739 989059837 965406627 965406638 996198971 996199031 699503869 699503885 327766213 327766305 553075291 553075356 660027495 660027587 717696828 717696902 340133195 340133214 78764116 78764188 480829100 480829147 365257404 365257415 414701171 414701217 673569628 673569670 986930601 986930680 931822006 931822061 559736489 559736571 278592588 278592672 991081815 991081824 382812359 382812422 783482414 783482431 827116449 827116548 510358640 510358682 983309834 983309924 173325291 173325367 69310476 69310558 328693561 328693588 397809555 397809642 427120375 427120378 805600735 805600816 379400351 379400433 293676699 293676749 146256882 146256893 295229121 295229212 817695868 817695957 439522215 439522296 209551403 209551452 760558451 760558507 102692830 102692872 768592780 768592864 336618419 336618514 159397301 159397384 940984302 940984309 86443508 86443603 153109374 153109399 746157759 746157787 170504878 170504918 270794297 270794303 251255278 251255350 854764004 854764031 449908301 449908372 658592288 658592289 775694657 775694746 842589014 842589081 164282344 164282417 435470928 435470996 299531826 299531853 941632198 941632274 132760025 132760106 102274020 102274101 432184308 432184358 149991618 149991694 259428767 259428850 872048648 872048675 942675751 942675829 868521398 868521457 319168432 319168492 889050450 889050535 500306273 500306282 608780023 608780067 357453314 357453358 983850504 983850537 353256071 353256139 35898493 35898584 81516813 81516833 291253449 291253521 990437598 990437669 709014776 709014828 810515309 810515343 395562526 395562626 306991825 306991845 105786445 105786468 280808166 280808230 523420978 523420995 281143450 281143543 78926573 78926626 16244534 16244630 777179072 777179142 696689189 696689268 690900504 690900520 411954064 411954078 793913484 793913520
Output: 1

Constraints:

1 <= n <= 2342; 0 <= s < e <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.