QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104756#6334. Passport________a____6 870ms113612kbC++142.4kb2023-05-11 21:16:312023-05-11 21:16:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 21:16:33]
  • 评测
  • 测评结果:6
  • 用时:870ms
  • 内存:113612kb
  • [2023-05-11 21:16:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010<<2
int n,N;
#define ls p<<1
#define rs p<<1|1
vector<int> ver[MAXN],e[MAXN];
int data[MAXN];
inline void add(int u,int v,int w){
	ver[u].push_back(v);
	//if(!w) cout<<u<<' '<<v<<endl;
	e[u].push_back(w);
}
void build(int l,int r,int p){
	if(l==r){
		data[p]=l;
		return ;
	}
	data[p]=++N;
	int mid=l+r>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	add(data[ls],data[p],0),add(data[rs],data[p],0);
}
void add(int l,int r,int x,int y,int p,int u){
	//for(int i=l;i<=r;i++){
	//	add(i,u,1);
	//}
	//return ;
	if(x<=l&&r<=y) {
		//cout<<l<<' '<<r<<' '<<u<<endl;
		return add(data[p],u,1);
	}
	int mid=l+r>>1;
	if(mid>=x) add(l,mid,x,y,ls,u);
	if(mid<y) add(mid+1,r,x,y,rs,u);
}
int dis1[MAXN],dis2[MAXN];
deque<int> q;
int vis[MAXN];
inline void dij1(){
	memset(dis1,0x3f,sizeof dis1);
	memset(vis,0,sizeof vis);
	dis1[1]=0;
	q.push_back(1);
	vis[1]=1;
	int u,v;
	while(!q.empty()){
		u=q.front(),q.pop_front();
		for(int i=0;i<ver[u].size();i++) {
			if(vis[v=ver[u][i]]) continue ;
			dis1[v]=dis1[u]+e[u][i];
			if(e[u][i]) q.push_back(v);
			else q.push_front(v);
			vis[v]=1;
		}
	}
}
inline void dij2(){
	memset(dis2,0x3f,sizeof dis2);
	memset(vis,0,sizeof vis);
	dis2[n]=0;
	q.push_back(n);
	vis[n]=1;
	int u,v;
	while(!q.empty()){
		u=q.front(),q.pop_front();
		for(int i=0;i<ver[u].size();i++) {
			if(vis[v=ver[u][i]]) continue ;
			dis2[v]=dis2[u]+e[u][i];
			if(e[u][i]) q.push_back(v);
			else q.push_front(v);
			vis[v]=1;
		}
	}
}
#define q Q
int ans[MAXN];
priority_queue<pair<int,int> > q;
inline void dij(){
	memset(vis,0,sizeof vis);
	for(int i=1;i<=N;i++) {
		ans[i]=dis1[i]+dis2[i];
		//cout<<dis1[i]<<' '<<dis2[i]<<' '<<ans[i]<<endl;
		q.push(make_pair(-ans[i],i));
	}
	int u,v;
	while(!q.empty()){
		u=q.top().second,q.pop();
		if(vis[u]) continue ;
		vis[u]=1;
		for(int i=0;i<ver[u].size();i++) {
			if(ans[v=ver[u][i]]<=ans[u]+e[u][i]) continue ;
			ans[v]=ans[u]+e[u][i];
			q.push(make_pair(-ans[v],v));
		}
	}
}
#undef q
signed main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	N=n;
	build(1,n,1);
	for(int i=1,l,r;i<=n;i++){
		scanf("%d%d",&l,&r);
		add(1,n,l,r,1,i);
	}
	int T;
	scanf("%d",&T);
	dij1(),dij2();
	dij();
	int x;
	while(T--){
		scanf("%d",&x);
		if(ans[x]>n) ans[x]=-1;
		printf("%d\n",ans[x]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 12ms
memory: 50572kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 7ms
memory: 50536kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 788ms
memory: 109224kb

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:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 300ms
memory: 87724kb

input:

198001
1 17
1 19
1 4
2 20
3 15
6 10
1 20
3 9
3 9
10 19
6 27
8 29
12 24
3 23
8 23
16 19
11 23
1 19
13 30
19 32
4 28
15 33
23 33
8 36
16 30
23 40
11 42
27 34
20 30
21 36
31 39
30 35
32 33
29 48
27 43
33 41
25 53
28 51
29 56
37 55
35 54
36 52
35 44
31 58
36 54
42 56
47 49
41 59
37 64
44 50
34 55
41 56
...

output:

15219

result:

ok single line: '15219'

Test #5:

score: 0
Accepted
time: 222ms
memory: 82380kb

input:

200000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
16 18
17 19
18 20
19 21
20 22
21 23
22 24
23 25
24 26
25 27
26 28
27 29
28 30
29 31
30 32
31 33
32 34
33 35
34 36
35 37
36 38
37 39
38 40
39 41
40 42
41 43
42 44
43 45
44 46
45 47
46 48
47 49
48 50
49 51
50 52
51 53...

output:

199999

result:

ok single line: '199999'

Test #6:

score: 0
Accepted
time: 189ms
memory: 89204kb

input:

195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195...

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 134ms
memory: 89176kb

input:

156789
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 783...

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 16
Accepted
time: 8ms
memory: 50504kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 11ms
memory: 50512kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 20ms
memory: 50552kb

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: 13ms
memory: 50532kb

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: 24
Accepted
time: 4ms
memory: 51180kb

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:

4

result:

ok single line: '4'

Test #20:

score: -24
Wrong Answer
time: 21ms
memory: 51092kb

input:

2486
1 12
2 8
1 7
3 12
2 11
3 15
1 8
4 11
9 15
3 21
11 13
4 15
9 21
9 19
5 15
8 20
8 25
16 24
11 29
11 23
18 23
14 32
17 24
13 27
15 30
21 34
16 29
20 35
19 32
29 34
20 39
21 43
29 40
28 43
26 44
31 45
28 43
35 38
30 40
37 46
40 43
42 42
42 45
43 54
39 51
40 51
45 54
46 57
39 53
47 53
47 54
41 59
49...

output:

315

result:

wrong answer 1st lines differ - expected: '314', found: '315'

Subtask #4:

score: 0
Wrong Answer

Test #28:

score: 8
Accepted
time: 15ms
memory: 51212kb

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
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
4
4
3
4
4
3
4
3
4
4
4
3
5
4
4
3
4
4
4
4
4
-1
3
4
4
3
3
4
4
4
3
3
4
4
3
-1
3
4
4
4
3
-1
4
4
4
3
4
4
4
4
4
4
3
3
4
5
4
3
3
4
4
3
4
4
3
4
3
4
4
-1
-1
3
4
4
3
4
4
3
4
3
4
5
4
4
4
4
3
4
4
4
3
4
5
4
4
4
4
4
3
4
4
4
4
4
4
4
3
4
4
4
-1
4
3
3
3
4
4
4
5
4
4
3
4
4
5
-1
4
4
4
4...

result:

ok 2419 lines

Test #29:

score: -8
Wrong Answer
time: 7ms
memory: 51128kb

input:

2500
1 7
1 6
1 8
1 15
5 14
2 17
5 18
8 17
2 13
3 12
3 14
12 22
4 15
6 18
14 16
8 20
6 22
10 22
12 28
11 28
20 24
12 33
16 29
23 28
20 28
19 35
18 30
24 39
20 33
19 33
30 40
23 32
26 37
28 36
30 45
35 40
36 41
34 44
34 46
29 44
37 50
33 44
39 49
35 54
40 54
39 46
36 50
47 54
44 49
46 61
42 58
41 58
4...

output:

314
314
314
314
315
315
315
315
315
315
315
315
315
315
315
314
314
314
314
314
315
314
315
315
315
314
314
315
314
314
315
315
315
315
314
315
315
315
315
314
314
315
315
314
314
315
314
315
315
314
314
314
314
314
314
314
315
314
314
314
314
314
315
315
315
315
314
315
314
314
314
314
314
314
314
...

result:

wrong answer 4th lines differ - expected: '313', found: '314'

Subtask #5:

score: 0
Wrong Answer

Test #33:

score: 0
Wrong Answer
time: 870ms
memory: 113612kb

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:

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

result:

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