QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235416#6334. Passport275307894a0 4ms12808kbC++141.8kb2023-11-02 19:00:272023-11-02 19:00:28

Judging History

This is the latest submission verdict.

  • [2023-11-02 19:00:28]
  • Judged
  • Verdict: 0
  • Time: 4ms
  • Memory: 12808kb
Show
  • [2023-11-02 19:00:27]
  • Submitted

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];
#define ls v<<1
#define rs v<<1|1
vector<int> S[N];
void BD(int l=1,int r=n,int v=1){
	S[v].clear();if(l==r) return;int m=l+r>>1;
	BD(l,m,ls);BD(m+1,r,rs);
}
void Add(int x,int y,int id,int l=1,int r=n,int v=1){
	if(x<=l&&r<=y) {S[v].emplace_back(id);return;}
	int m=l+r>>1;x<=m&&(Add(x,y,id,l,m,ls),0);y>m&&(Add(x,y,id,m+1,r,rs),0);
}
void BFS(int x,int *d){
	queue<int> q;
	BD();for(int i=1;i<=n;i++) Add(L[i],R[i],i);
	auto qry=[&](auto self,int x,int *d,int l=1,int r=n,int v=1)->void{
		for(int i:S[v]) if(d[i]>d[x]+1) q.emplace(i),d[i]=d[x]+1;
		S[v].clear();if(l==r) return;int m=l+r>>1;
		x<=m?self(self,x,d,l,m,ls):self(self,x,d,m+1,r,rs);
	};
	if(x){
		fill(d+1,d+n+1,INF);
		for(int i=1;i<=n;i++) if(L[i]<=x&&x<=R[i]) d[i]=1,q.emplace(i);
	} 
	else for(int i=1;i<=n;i++) q.emplace(i);
	while(!q.empty()){
		int x=q.front();q.pop();
		qry(qry,x,d);
	}
}
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]-1;
	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]);
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 6
Accepted
time: 0ms
memory: 11048kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 10944kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: -6
Runtime Error

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: 0ms
memory: 11100kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 2ms
memory: 10624kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 2ms
memory: 11080kb

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: 11116kb

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: 0ms
memory: 11796kb

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: 3ms
memory: 12808kb

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: 0
Wrong Answer
time: 4ms
memory: 11688kb

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

result:

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

Subtask #5:

score: 0
Runtime Error

Test #33:

score: 0
Runtime Error

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:
English 繁體中文 简体中文

Server Time: 2025-02-28 10:10:56 | OpenSource Project