QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235387#6334. Passport275307894a0 28ms5860kbC++141.2kb2023-11-02 18:32:112023-11-02 18:32:11

Judging History

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

  • [2023-11-02 18:32:11]
  • 评测
  • 测评结果:0
  • 用时:28ms
  • 内存:5860kb
  • [2023-11-02 18:32:11]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,L[N],R[N];
int d1[N],d2[N],d[N];
void BFS(int x,int *d){
	queue<int> q;
	if(x) fill(d+1,d+n+1,INF),d[x]=0,q.emplace(x);
	else for(int i=1;i<=n;i++) q.emplace(i);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=1;i<=n;i++) if(L[i]<=x&&x<=R[i]&&d[i]>d[x]+1) d[i]=d[x]+1,q.emplace(i); 
	}
}
int main(){
	int i,j,h;scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
	BFS(1,d1);BFS(n,d2);
	for(i=1;i<=n;i++) d[i]=d1[i]+d2[i];
	BFS(0,d);
	int q;scanf("%d",&q);while(q--){
		int x;scanf("%d",&x);
		printf("%d\n",d[x]>n+1?-1:d[x]);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 6
Accepted
time: 1ms
memory: 5736kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: -6
Time Limit Exceeded

input:

196001
1 408
2 37822
1 1221
1 160899
4 62751
3 21706
2 4118
8 70696
8 4916
3 24286
9 443
8 171744
11 170980
7 3541
12 16428
8 71164
1 186827
11 234
2 23141
4 17143
21 9522
10 24
19 15936
3 15884
17 426
14 3188
17 168317
4 1560
25 35
16 39439
21 122
4 17507
8 97645
11 824
25 59856
30 9265
7 151420
37...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 16
Accepted
time: 1ms
memory: 3644kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 1ms
memory: 5848kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 5728kb

input:

6
1 1
2 2
1 3
3 5
5 6
1 6
1
4

output:

3

result:

ok single line: '3'

Test #11:

score: -16
Wrong Answer
time: 0ms
memory: 3760kb

input:

9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

output:

4

result:

wrong answer 1st lines differ - expected: '3', found: '4'

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 28ms
memory: 5860kb

input:

2337
1 3
2 77
1 1397
2 222
3 62
6 1896
7 10
6 950
9 9
10 16
11 455
9 588
13 16
7 1245
9 1342
8 1727
7 122
11 653
9 1094
2 57
11 81
19 1290
6 1584
16 79
14 215
21 61
27 27
16 1458
16 198
26 180
31 31
11 240
33 36
11 121
34 1542
9 1752
14 456
36 43
36 2244
40 40
4 517
42 662
31 1350
33 162
30 843
28 1...

output:

5

result:

wrong answer 1st lines differ - expected: '4', found: '5'

Subtask #4:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 27ms
memory: 5724kb

input:

2419
1 883
1 29
3 41
4 2201
1 808
6 45
7 1456
6 134
6 1372
1 1776
4 441
7 208
5 28
4 604
7 56
9 617
8 2115
15 60
13 456
10 2071
18 23
18 39
5 39
21 35
4 75
25 44
24 640
21 30
4 860
30 31
18 78
32 779
1 927
33 34
19 59
34 181
21 502
23 155
39 39
2 254
30 641
42 50
10 2000
41 2220
18 632
35 48
27 905
...

output:

3
4
4
4
4
4
4
4
4
3
4
4
4
4
4
4
4
5
5
4
5
5
4
5
4
5
5
5
4
6
5
5
4
5
5
5
5
5
-1
4
5
5
4
4
5
5
5
4
4
5
5
4
-1
4
5
5
5
4
-1
5
5
5
4
5
5
5
5
5
5
4
4
5
6
5
4
4
5
5
4
5
5
4
5
4
5
5
-1
-1
4
5
5
4
5
5
4
5
4
5
6
5
5
5
5
4
5
5
5
4
5
6
5
5
5
5
5
4
5
5
5
5
5
5
5
4
5
5
5
-1
5
4
4
4
5
5
5
6
5
5
4
5
5
6
-1
5
5
5
5...

result:

wrong answer 2nd lines differ - expected: '3', found: '4'

Subtask #5:

score: 0
Time Limit Exceeded

Test #33:

score: 0
Time Limit Exceeded

input:

196830
1 67357
2 183304
3 23390
4 54
1 145887
3 27807
3 12376
1 1013
3 113274
3 191874
6 23342
9 2113
13 94245
3 141449
10 1727
3 51
17 99028
6 193803
8 7452
6 121537
9 23658
18 611
6 4756
4 5141
8 8547
8 66922
13 7021
9 72
3 53043
16 167381
2 15530
5 192
33 33
9 92655
10 36182
20 19992
36 24454
1 6...

output:


result: