QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563410#4206. Event Hoppinghansiyuan0 61ms29816kbC++141.4kb2024-09-14 11:25:312024-09-14 11:25:32

Judging History

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

  • [2024-09-14 11:25:32]
  • 评测
  • 测评结果:0
  • 用时:61ms
  • 内存:29816kb
  • [2024-09-14 11:25:31]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m;
int L[N],R[N],pos[N];
int f0[N][20],g0[N][20];
int f[N][20];
struct nd{int l,r,id;} eve[N];
bool cmp(nd x,nd y){return x.r<y.r;}
int mn=1e9,mnh;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&L[i],&R[i]);
		eve[i] = {L[i],R[i],i};
	}
	sort(eve+1,eve+n+1,cmp);
	for(int i=1;i<=n;i++){
		pos[eve[i].id] = i;
		f0[i][0] = eve[i].l;
		g0[i][0] = i;
	}
	for(int j=1;j<=17;j++)
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(f0[i][j-1] < f0[i+(1<<j-1)][j-1])
				f0[i][j]=f0[i][j-1], g0[i][j]=g0[i][j-1];
			else
				f0[i][j]=f0[i+(1<<j-1)][j-1], g0[i][j]=g0[i+(1<<j-1)][j-1];
		}
	for(int i=1;i<=n;i++){
		int l=1,r=i;
		while(l<r){
			int mid = (l+r)>>1;
			if(eve[mid].r>=eve[i].l) r=mid;
			else l=mid+1;
		}
		int t = log2(i-l+1);
		if(f0[l][t] < f0[i-(1<<t)+1][t]) f[i][0]=g0[l][t];
		else f[i][0]=g0[i-(1<<t)+1][t];
	}
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			f[i][j] = f[f[i][j-1]][j-1];
	while(m--){
		int s,t;
		scanf("%d%d",&s,&t);
		if(R[s]>R[t]) {puts("impossible"); continue;}
		int ans=0;
		int x = pos[t];
		for(int j=17;j>=0;j--)
			if(eve[f[x][j]].l>L[s]){
				ans += (1<<j);
				x = f[x][j];
			}
		if(eve[x].l>L[s]) ans++,x=f[x][0];
		if(eve[x].l>L[s]) {puts("impossible"); continue;}
		if(x!=pos[s]) ans++,x=pos[s];
		printf("%d\n",ans);
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 59ms
memory: 29792kb

input:

100000 100000
825913690 825916363
333322014 333324481
302015784 302018251
841002775 841005448
810249910 810252583
803554045 803556718
379590599 379593066
413477311 413479778
304105333 304107800
856802878 856805551
355907399 355909866
365590374 365592841
813775597 813778270
816058339 816061012
383873...

output:

1
impossible
1
impossible
impossible
impossible
31336
impossible
impossible
impossible
impossible
27166
16274
impossible
impossible
impossible
impossible
impossible
impossible
21353
17890
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
67...

result:

ok 100000 lines

Test #2:

score: 10
Accepted
time: 60ms
memory: 29816kb

input:

100000 100000
389680865 389680885
532001242 532004287
460483812 460491583
691010527 691018298
489353103 489356770
593534107 593537042
509433341 509441112
846177578 846179089
586840272 586848043
834393248 834401019
474044207 474051978
614427322 614435093
574678657 574686428
557256443 557262524
502657...

output:

80801
80800
80800
80799
80799
80799
80798
80798
80798
80798
80797
80797
80797
80797
impossible
80796
80796
80796
80796
impossible
80797
80795
80795
80795
80795
impossible
80796
80796
80794
80794
80794
80794
impossible
80795
80795
80795
80794
80793
80793
80793
impossible
80794
80794
80794
80794
80793...

result:

ok 100000 lines

Test #3:

score: 10
Accepted
time: 36ms
memory: 29684kb

input:

100000 100000
1 2
1 2
5 6
5 6
9 10
9 10
13 14
13 14
17 18
17 18
21 22
21 22
25 26
25 26
29 30
29 30
33 34
33 34
37 38
37 38
41 42
41 42
45 46
45 46
49 50
49 50
53 54
53 54
57 58
57 58
61 62
61 62
65 66
65 66
69 70
69 70
73 74
73 74
77 78
77 78
81 82
81 82
85 86
85 86
89 90
89 90
93 94
93 94
97 98
97...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 lines

Test #4:

score: 10
Accepted
time: 59ms
memory: 29816kb

input:

100000 100000
407280099 407284136
197925316 197929353
463232919 463236956
248771331 248775368
314921613 314925650
454125447 454129484
215159269 215163306
376796712 376800749
343418796 343422833
126014235 126018272
315022538 315026575
242069911 242073948
479849211 479853248
414950399 414954436
254079...

output:

99999
99998
99998
99997
99997
99997
99996
99996
99996
99996
99995
99995
99995
99995
99995
99994
99994
99994
99994
99994
99994
99993
99993
99993
99993
99993
99993
99993
99992
99992
99992
99992
99992
99992
99992
99992
99991
99991
99991
99991
99991
99991
99991
99991
99991
99990
99990
99990
99990
99990
...

result:

ok 100000 lines

Test #5:

score: 10
Accepted
time: 61ms
memory: 29696kb

input:

100000 100000
861047815 861052922
578273225 578278332
622183211 622188318
822908739 822913846
546318726 546323833
461573168 461578275
480101364 480106471
456455954 456461061
575234560 575239667
464851862 464856969
897159412 897164519
722826860 722831967
755036709 755041816
811213709 811218816
445680...

output:

99999
99997
99995
99993
99991
99989
99987
99985
99983
99981
99979
99977
99975
99973
99971
99969
99967
99965
99963
99961
99959
99957
99955
99953
99951
99949
99947
99945
99943
99941
99939
99937
99935
99933
99931
99929
99927
99925
99923
99921
99919
99917
99915
99913
99911
99909
99907
99905
99903
99901
...

result:

ok 100000 lines

Test #6:

score: 10
Accepted
time: 48ms
memory: 29620kb

input:

100000 100000
107067593 107068563
375121029 375132523
244489164 244489510
371625987 371628227
63502583 63505678
622119714 622149239
792197805 792202711
692512281 692515198
196552919 196554193
677923903 677926489
680041239 680046357
697562945 697565212
206418851 206420890
410143641 410145269
63943786...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 lines

Test #7:

score: 10
Accepted
time: 1ms
memory: 12140kb

input:

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

output:

3
4
impossible
0
impossible

result:

ok 5 lines

Test #8:

score: 10
Accepted
time: 53ms
memory: 29800kb

input:

100000 100000
432053319 432056406
486393780 486396867
318945639 318948726
557737437 557740524
505903620 505906707
312861162 312864249
530084091 530087178
378401259 378404346
590749815 590752902
384158514 384161601
397824663 397827750
305937021 305940108
418238994 418242081
311718972 311722059
421174...

output:

99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
...

result:

ok 100000 lines

Test #9:

score: 10
Accepted
time: 57ms
memory: 29736kb

input:

100000 100000
460767811 460773658
363280780 363286627
318744181 318750028
587618476 587624323
349815139 349820986
654104713 654110560
522640765 522646612
667874398 667880245
722245651 722251498
442864297 442870144
522664153 522670000
660805375 660811222
710639356 710645203
484196740 484202587
355358...

output:

77828
77828
77829
77828
77829
77827
77827
77829
77827
77826
77826
77828
77827
77826
77825
77825
77827
77826
77826
77825
impossible
77824
77826
77825
77825
77825
impossible
77824
77824
77825
77824
77824
77824
impossible
77824
77823
77823
77825
77823
77823
77823
impossible
77824
77823
77822
77823
7782...

result:

ok 100000 lines

Test #10:

score: 0
Wrong Answer
time: 45ms
memory: 29656kb

input:

100000 100000
639515864 639521231
667143094 667144538
647258206 647258690
462233258 462234230
475801547 475802613
524127311 524128428
543287190 543289381
535841282 535843238
585211823 585213845
734658645 734658899
537776171 537783441
730349191 730354503
616233528 616234443
679161417 679162801
660817...

output:

1
1
impossible
1
impossible
impossible
1
impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
impossibl...

result:

wrong answer 3rd lines differ - expected: '2', found: 'impossible'

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 2ms
memory: 12040kb

input:

1000 100
67878298 387720407
270457472 922959000
286470357 618323410
260791474 282940414
301337446 553875076
478221503 724555102
380447228 437131400
191801427 465825895
366088873 431222136
49483883 103442781
699926238 720636919
253150351 291688158
411085513 727726933
444078045 496386017
420626857 822...

output:

1
2
2
impossible
1
2
1
2
impossible
2
2
impossible
impossible
impossible
2
impossible
impossible
impossible
impossible
impossible
2
impossible
2
impossible
1
1
impossible
1
1
2
1
impossible
2
impossible
2
impossible
1
2
impossible
impossible
impossible
2
2
impossible
impossible
2
2
impossible
imposs...

result:

wrong answer 15th lines differ - expected: '1', found: '2'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 49ms
memory: 29764kb

input:

100000 100000
903318459 905410836
903528407 905653109
925180437 927048927
473524826 475597377
362562616 364539688
644980844 646918450
242583398 244653279
506338025 508361063
481496693 483530832
970053326 972147109
794840350 796900045
130664210 132709680
634100524 636336820
844429264 846504591
652483...

output:

500
501
500
501
501
500
501
501
501
500
501
501
501
501
500
501
501
501
501
501
500
501
501
501
501
501
501
500
501
501
501
501
501
501
501
500
501
501
501
501
501
501
501
501
500
501
501
501
501
501
501
501
501
501
500
501
501
501
501
501
501
501
501
501
501
500
501
501
501
501
501
501
501
501
501
...

result:

wrong answer 2nd lines differ - expected: '500', found: '501'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%