QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644162#1429. HitFlamireTL 591ms5972kbC++171.3kb2024-10-16 11:27:122024-10-16 11:27:13

Judging History

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

  • [2024-10-16 11:27:13]
  • 评测
  • 测评结果:TL
  • 用时:591ms
  • 内存:5972kb
  • [2024-10-16 11:27:12]
  • 提交

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...

result: