QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644162 | #1429. Hit | Flamire | TL | 591ms | 5972kb | C++17 | 1.3kb | 2024-10-16 11:27:12 | 2024-10-16 11:27:13 |
Judging History
answer
#include <bits/stdc++.h>
#define N 200011
using namespace std;
vector<int> vv;
struct edge{int u,v,w;};
int dis[N],X,t,n,l[N],r[N];vector<edge> ve;
int F(int w){return w==1?X:w;}
bool BF()
{
for(int i=0;i<vv.size();++i)dis[i]=0;
for(int _=0;_<vv.size();++_)
{
bool ok=0;
for(edge e:ve)if(dis[e.v]>dis[e.u]+F(e.w))dis[e.v]=dis[e.u]+F(e.w),ok=1;
if(!ok)return 1;
}
return 0;
}
int main()
{
scanf("%d",&t);while(t--)
{
scanf("%d",&n);vv.clear();ve.clear();
for(int i=1;i<=n;++i)scanf("%d%d",l+i,r+i),vv.push_back(l[i]-1),vv.push_back(r[i]);
sort(vv.begin(),vv.end());vv.resize(unique(vv.begin(),vv.end())-vv.begin());
for(int i=0;i+1<vv.size();++i)ve.push_back({i+1,i,0});
for(int i=1;i<=n;++i)
{
int idl=lower_bound(vv.begin(),vv.end(),l[i]-1)-vv.begin();
int idr=lower_bound(vv.begin(),vv.end(),r[i])-vv.begin();
ve.push_back({idr,idl,-1});
ve.push_back({idl,idr,1});
}
int L=1,R=n,ans=0;
while(L<=R)
{
X=L+R>>1;
if(BF())ans=X,R=X-1;else L=X+1;
}
printf("%d ",X=ans);
BF();
int mn=1e9;
for(int i=0;i<vv.size();++i)mn=min(mn,dis[i]);
printf("%d ",-mn);
for(int i=1;i<vv.size();++i)if(dis[i]!=dis[i-1])printf("%d ",vv[i]);putchar(10);
}
fclose(stdin);fclose(stdout);return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
4 4 0 1 2 3 4 5 3 5 5 0 70 0 10 20 30 40 50 60 70 8 -1 7 -2 -1 -9 -7 -8 9 -9 -7 -2 4 -7 4 3 9 5 0 1 0 2 2 3 3 5 4 5
output:
1 3 1 2 5 4 4 10 30 50 70 2 3 -9 -2 4 2 3 1 2 5
result:
ok ok, tt = 4
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 1 0 1
output:
1 1 1
result:
ok ok, tt = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
3 1 -1000000000 1000000000 1 -1000000000 -999999999 1 999999999 1000000000
output:
1 1 1000000000 1 1 -999999999 1 1 1000000000
result:
ok ok, tt = 3
Test #4:
score: 0
Accepted
time: 40ms
memory: 5896kb
input:
100000 1 -755794993 -744839313 1 638832683 645984490 1 333736843 342792055 1 -412526164 -400411740 1 193156287 205856204 1 266085745 268256106 1 789502967 806620391 1 85305828 86560242 1 -655573585 -644094805 1 517734490 518776542 1 -966001098 -958188900 1 -780504491 -762439365 1 -896592598 -8804653...
output:
1 1 -744839313 1 1 645984490 1 1 342792055 1 1 -400411740 1 1 205856204 1 1 268256106 1 1 806620391 1 1 86560242 1 1 -644094805 1 1 518776542 1 1 -958188900 1 1 -762439365 1 1 -880465378 1 1 -545603970 1 1 674193870 1 1 -613177432 1 1 -189815796 1 1 -636284766 1 1 -212256845 1 1 -...
result:
ok ok, tt = 100000
Test #5:
score: 0
Accepted
time: 39ms
memory: 3932kb
input:
100000 1 -392749917 -319069731 1 761382535 804248178 1 -858764838 -819815600 1 -87503649 -20800126 1 -69252318 64456029 1 -848092983 -666742404 1 -659061625 -620054847 1 -982031817 -883932130 1 -47104919 97672798 1 -494834028 -456770262 1 496748206 692802903 1 572757539 669651153 1 -484466016 -41314...
output:
1 1 -319069731 1 1 804248178 1 1 -819815600 1 1 -20800126 1 1 64456029 1 1 -666742404 1 1 -620054847 1 1 -883932130 1 1 97672798 1 1 -456770262 1 1 692802903 1 1 669651153 1 1 -413146928 1 1 912121104 1 1 -402000624 1 1 310772000 1 1 -329279769 1 1 888975125 1 1 -505832802 1 1 310...
result:
ok ok, tt = 100000
Test #6:
score: 0
Accepted
time: 39ms
memory: 3904kb
input:
100000 1 -422738609 -95619025 1 496655203 761501973 1 -253341552 895113150 1 -213934938 560617332 1 257193179 510136024 1 -684784337 -650911183 1 -999254900 62633326 1 -627557633 641989470 1 -682383675 66116491 1 -859630523 340664034 1 -422590930 433070710 1 259879968 316877801 1 -90014752 991378355...
output:
1 1 -95619025 1 1 761501973 1 1 895113150 1 1 560617332 1 1 510136024 1 1 -650911183 1 1 62633326 1 1 641989470 1 1 66116491 1 1 340664034 1 1 433070710 1 1 316877801 1 1 991378355 1 1 351139472 1 1 643790197 1 1 899761936 1 1 -713126923 1 1 358738130 1 1 502116510 1 1 647513652 ...
result:
ok ok, tt = 100000
Test #7:
score: 0
Accepted
time: 39ms
memory: 5972kb
input:
100000 1 -146170891 -135832850 1 -758721094 -739814745 1 434418655 436843128 1 584625787 597671579 1 -54920782 -48746711 1 -890924962 -874340357 1 -955254050 -945006677 1 276114326 279390556 1 -291805472 -288200984 1 673823575 685514644 1 -43237398 -31640268 1 -239622315 -224829882 1 -596965402 -595...
output:
1 1 -135832850 1 1 -739814745 1 1 436843128 1 1 597671579 1 1 -48746711 1 1 -874340357 1 1 -945006677 1 1 279390556 1 1 -288200984 1 1 685514644 1 1 -31640268 1 1 -224829882 1 1 -595948258 1 1 -886772435 1 1 281278372 1 1 -154122163 1 1 302173751 1 1 117393731 1 1 -725867793 1 1 -...
result:
ok ok, tt = 100000
Test #8:
score: 0
Accepted
time: 39ms
memory: 3796kb
input:
100000 1 -938525664 -817076126 1 -932701889 -823854498 1 -198817321 -90954343 1 852989237 895167117 1 -657597128 -592296022 1 -189337058 -60845257 1 -308394755 -143079067 1 -798793040 -658589397 1 587269730 632505978 1 463959892 651681553 1 210139744 354710208 1 -738322653 -579254528 1 -473167271 -4...
output:
1 1 -817076126 1 1 -823854498 1 1 -90954343 1 1 895167117 1 1 -592296022 1 1 -60845257 1 1 -143079067 1 1 -658589397 1 1 632505978 1 1 651681553 1 1 354710208 1 1 -579254528 1 1 -415805150 1 1 -620402885 1 1 -80905695 1 1 866571582 1 1 884604855 1 1 888448333 1 1 -97223882 1 1 791...
result:
ok ok, tt = 100000
Test #9:
score: 0
Accepted
time: 39ms
memory: 3804kb
input:
100000 1 -124550996 175843021 1 -993480749 369513273 1 -472345946 866834459 1 51146719 619481540 1 -953985291 -388861986 1 30060232 86153621 1 397966610 670657620 1 228037899 527397835 1 -328812046 777147616 1 528770087 999819348 1 -443642177 430027557 1 -985366041 937429463 1 286165886 375753871 1 ...
output:
1 1 175843021 1 1 369513273 1 1 866834459 1 1 619481540 1 1 -388861986 1 1 86153621 1 1 670657620 1 1 527397835 1 1 777147616 1 1 999819348 1 1 430027557 1 1 937429463 1 1 375753871 1 1 -241036764 1 1 253849507 1 1 904700981 1 1 875953108 1 1 121979058 1 1 465863397 1 1 901461978 ...
result:
ok ok, tt = 100000
Test #10:
score: 0
Accepted
time: 34ms
memory: 5908kb
input:
18139 4 -336270587 -330557331 -252002330 -239258910 -186846904 -186440987 848243159 868102416 3 -195461235 -180651308 -250893512 -232183484 741194405 748153230 1 -583374820 -573301094 2 -289487516 -278362438 -617984192 -600701104 3 361103576 377771047 -629713150 -625261223 760487909 765234419 2 -789...
output:
1 4 -330557331 -239258910 -186440987 868102416 1 3 -232183484 -180651308 748153230 1 1 -573301094 1 2 -600701104 -278362438 1 3 -625261223 377771047 765234419 1 2 -772865937 -84556628 1 1 770021135 1 4 -426773202 -230063854 446840121 522239063 1 3 -817483854 -666548915 382548322 1 6 -869109...
result:
ok ok, tt = 18139
Test #11:
score: 0
Accepted
time: 46ms
memory: 3908kb
input:
18100 8 598403417 795720309 -373919856 -307381953 199626892 235156246 -217973856 -203235401 516184634 548146965 556458253 612829986 -686678416 -587302321 -251190508 -105682769 6 -526414856 -462880667 -734369052 -596753646 114814523 150451126 -10532542 21149560 -892168032 -828869761 -663573167 -62124...
output:
1 6 -587302321 -307381953 -203235401 235156246 548146965 612829986 1 5 -828869761 -621240147 -462880667 21149560 150451126 1 1 342776419 1 5 -964969612 -855582387 -649355822 -35329612 188035491 1 6 -798024093 -606741869 437565320 567632562 803810143 964101989 1 3 -767627849 -495398605 400486568...
result:
ok ok, tt = 18100
Test #12:
score: 0
Accepted
time: 46ms
memory: 3920kb
input:
18133 3 -532740766 -492922415 -745044455 -386840345 -749335013 -565459391 5 -534228433 657736275 688238957 974882583 -927059249 -173514637 -821264333 -27208503 -637987799 201098089 2 -183611012 812265988 360179783 519406660 1 363751319 483623678 5 -417328703 863569501 -593491816 -478939136 -23407126...
output:
1 2 -745044456 -492922415 1 2 -173514637 974882583 1 1 519406660 1 1 483623678 1 2 -496651937 803485629 1 3 -767189089 -276389524 674646296 1 1 -337612608 2 4 -774316111 377059314 671197591 947062775 2 2 -357889994 375405984 1 2 -647977976 124238958 2 2 -224588367 239570222 1 4 -939414375...
result:
ok ok, tt = 18133
Test #13:
score: 0
Accepted
time: 51ms
memory: 3748kb
input:
10000 10 -161942485 -159394105 705139634 709295587 -483286727 -481478345 399306971 407340943 -217429921 -212103356 -12246787 21576 -125089225 -115526252 323652979 329876984 908529648 917523471 49320201 64121837 10 -744908257 -740112635 450103712 451805266 200334663 208816371 -996683991 -990727071 57...
output:
1 10 -481478345 -212103356 -159394105 -115526252 21576 64121837 329876984 407340943 709295587 917523471 1 10 -990727071 -966959227 -740112635 -486863445 208816371 281620256 369203597 451805266 517813073 588061967 1 10 -980020619 -897308380 -337399133 -291693182 -185627418 -62840400 15760740 322921...
result:
ok ok, tt = 10000
Test #14:
score: 0
Accepted
time: 51ms
memory: 5828kb
input:
10000 10 482432556 644827792 -702152771 -602096184 -169663783 -105112142 292039646 396589232 534340289 664863338 -422883760 -342513788 -97749687 -25660790 -390644233 -281643839 -810548734 -759031174 -673955416 -549979942 10 -119363544 6349651 122113020 133353790 -373106144 -289542973 -879113115 -689...
output:
1 7 -759031174 -602096184 -342513788 -105112142 -25660790 396589232 644827792 1 7 -689317566 -289542973 6349651 133353790 181128673 418090877 672522353 1 6 -835233568 -461990596 -179986756 -36565299 252510816 623612156 1 6 -796351540 -659766756 111484915 335210280 532838490 716462515 1 6 -805420...
result:
ok ok, tt = 10000
Test #15:
score: 0
Accepted
time: 49ms
memory: 3868kb
input:
10000 10 -658814387 373850938 43747648 576461378 -431503832 324268120 -385319430 112339593 -460475672 399479363 -178690792 207687233 -474720568 -234903445 -703397684 -146305358 262963282 912360651 -424445504 486778793 10 -928391058 -102691886 -917150287 689395688 -621563113 90008077 750906563 861653...
output:
2 3 -460475673 -146305358 399479363 3 3 -576674218 472435445 758884343 5 5 -684479450 -124002597 -74942502 145747514 194530530 1 5 -908439896 -610270887 -299953542 307981824 739861543 1 3 -740177142 -375349773 411568686 2 3 -797052731 -239925500 66648346 3 4 -877019032 -370784196 417530482 808...
result:
ok ok, tt = 10000
Test #16:
score: 0
Accepted
time: 340ms
memory: 3944kb
input:
2015 31 367803441 382779156 -163366000 -145324996 -305141801 -304156223 -425625552 -414986437 -170900678 -152771324 536906161 550613861 -688165350 -687718654 -225793776 -221963993 -331207650 -317565830 488620488 507260616 420866299 426676602 253541173 272809277 -174936617 -172183170 -715888891 -7149...
output:
1 25 -895078281 -790201899 -714949937 -687718654 -509165271 -464582157 -414986437 -411719929 -318020488 -304156223 -221963993 -172183170 -152771324 88750440 180607248 231004181 272809277 382779156 426676602 437793551 507260616 550613861 673246744 791549862 962718666 1 20 -766541093 -379369333 -1766...
result:
ok ok, tt = 2015
Test #17:
score: 0
Accepted
time: 268ms
memory: 5800kb
input:
1961 91 776129123 928989894 709599839 804296310 755486132 821491760 -416804447 -294950319 -795171418 -598953586 314046883 430976730 364193950 416986736 -338772962 -173803958 -437039989 -347296792 794012412 797301058 541168633 561063499 385768025 538260546 -636369000 -528032305 -518735967 -388173299 ...
output:
3 24 -870254092 -738831005 -602955231 -528032305 -472333424 -416804448 -300765402 -164563341 -139434963 -66559103 28874255 61513341 105513228 176869155 253526758 268775606 376945696 487121504 551617467 584364034 698845899 797301058 855002236 924934522 3 22 -896023510 -786442739 -713479999 -66193804...
result:
ok ok, tt = 1961
Test #18:
score: 0
Accepted
time: 258ms
memory: 5904kb
input:
1915 88 -599184315 73586345 -57063004 735370626 -594784261 657664800 -312883696 57445978 -285146469 851050384 625822943 834222116 68918244 794706645 -301544950 933777477 206867581 731025004 -439024607 -420997711 -270811554 773852696 -949479290 -530448879 -59150188 446557826 -979358741 -208839320 -18...
output:
10 11 -899632473 -751313206 -636400630 -430922015 -335044597 -76861914 48731604 234178055 543920429 625822942 731025004 10 12 -915135955 -869165463 -380228541 -353267015 -219810204 45521360 255831879 435111447 457764395 658060995 881964277 966321387 9 9 -874076743 -591706880 -409858630 -246141044 ...
result:
ok ok, tt = 1915
Test #19:
score: 0
Accepted
time: 591ms
memory: 3876kb
input:
1000 100 -167567106 -163456106 -645093441 -626354011 82584033 96043351 451690906 463599253 950908947 966920341 -982393168 -968113113 836738075 850385021 -707055272 -698612947 -171074009 -155730094 -352159178 -334298774 827292325 832177673 -554357876 -552869616 888998643 890253060 -218756361 -2053824...
output:
2 66 -982482176 -973277785 -905805828 -844196587 -815060372 -803486026 -731696490 -714637462 -702128929 -679644388 -652368218 -626354011 -610406258 -587864612 -581132298 -552869616 -534363363 -524329989 -511391771 -489599987 -477403870 -440003155 -334298774 -292093282 -224130272 -205382471 -18435661...
result:
ok ok, tt = 1000
Test #20:
score: 0
Accepted
time: 414ms
memory: 3872kb
input:
1000 100 -545312772 -482856294 -452625671 -373728742 -189286126 -27573154 438335850 461956201 -570840084 -394388626 -343214435 -277284691 742508809 929985121 173867778 353632110 -862386155 -731171646 -381279305 -233431288 -696987559 -615594564 635223307 770675002 125262736 126793885 -611209204 -5383...
output:
3 27 -958685777 -927802231 -830171223 -798470228 -694138247 -596668396 -482892644 -405668244 -313456988 -233431288 -134456749 -51277528 16070551 71274229 119909448 126793885 173867777 266692791 322489689 388734009 440058972 487045106 541241172 615808401 684118563 799598479 842921701 4 27 -932547827...
result:
ok ok, tt = 1000
Test #21:
score: 0
Accepted
time: 376ms
memory: 3848kb
input:
1000 100 -514015364 -502468776 -780221896 -332795155 -798142427 -562846508 -535018850 875423486 436197708 544762002 -931471806 -838065195 -448363432 53489617 -969136873 -123865150 -555197110 -130170596 -163510682 857998125 -474465124 -359095545 -830847377 -93005735 -779554592 -580059164 -338261122 9...
output:
12 13 -861437752 -625110298 -507100582 -467725250 -317950871 -170751408 -41526042 266426286 328548343 400839272 446150542 628282309 796458750 11 11 -859746466 -786246949 -741956569 -639282140 -265180880 -84711899 20616329 208696746 365901709 643755723 855025222 11 13 -922662371 -864317710 -6614091...
result:
ok ok, tt = 1000
Test #22:
score: -100
Time Limit Exceeded
input:
196 512 -976710587 -957911716 396126887 413364569 -224591467 -213982089 -870349990 -867867294 875985077 891894871 -479834146 -475222581 -739569971 -735475587 176524306 179708881 772080172 773719956 -483049430 -467425107 554653646 569597668 625892984 636319270 607058779 622167287 575940568 578213647 ...
output:
3 182 -992975234 -980206931 -974677788 -969109156 -959298474 -946394706 -945103384 -927901186 -911013309 -899479310 -884414817 -872173855 -867867294 -850786484 -832674011 -816657720 -801199912 -791767221 -774570464 -748847474 -738274138 -726221462 -720469771 -703464216 -702637729 -679341018 -6685945...