QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#235392	#6334. Passport	275307894a	48	1050ms	6208kb	C++14	1.2kb	2023-11-02 18:35:49	2023-11-02 18:35:49

Judging History

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

[2023-11-02 18:35:49]
评测

测评结果：48
用时：1050ms
内存：6208kb

查看

[2023-11-02 18:35:49]
提交

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);
		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();
		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]-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

Time Limit Exceeded

Test #1:

score: 6

Accepted

time: 1ms

memory: 5920kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 6176kb

input:

output:

result:

ok single line: '1'

Test #3:

score: -6

Time Limit Exceeded

input:

output:

result:

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 0ms

memory: 3856kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 1ms

memory: 6176kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5920kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 0ms

memory: 5920kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5844kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 1ms

memory: 5916kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 1ms

memory: 6196kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 1ms

memory: 5916kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 1ms

memory: 5920kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 1ms

memory: 5928kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 3ms

memory: 6176kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 28ms

memory: 5928kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 19ms

memory: 4008kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 58ms

memory: 5936kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 43ms

memory: 5916kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 17ms

memory: 6024kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 1050ms

memory: 5928kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 14ms

memory: 6012kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 27ms

memory: 6024kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 14ms

memory: 5956kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 30ms

memory: 5940kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 19ms

memory: 5940kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 18ms

memory: 6208kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 1033ms

memory: 5884kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 0

Accepted

time: 23ms

memory: 5944kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 0

Time Limit Exceeded

Test #33:

score: 0

Time Limit Exceeded

input: