QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#353095	#6334. Passport	zyz07	100 ✓	375ms	95852kb	C++17	2.0kb	2024-03-13 21:02:56	2024-03-13 21:02:56

Judging History

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

[2024-03-13 21:02:56]
评测

测评结果：100
用时：375ms
内存：95852kb

查看

[2024-03-13 21:02:56]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2e5+5;
int n,L[N],R[N],q,disl[N*5],disr[N*5],dis[N*5],tot;
vector<pair<int,int>> g[N*5];
struct SegmentTree{
	int poi[N*4];
	void init(int p=1,int L=1,int R=n){
		if(L==R){
			poi[p]=L;
			return;
		}
		int mid=(L+R)/2;
		poi[p]=++tot;
		init(p*2,L,mid);
		init(p*2+1,mid+1,R);
		g[poi[p*2]].emplace_back(poi[p],0);
		g[poi[p*2+1]].emplace_back(poi[p],0);
	}
	void link(int l,int r,int u,int p=1,int L=1,int R=n){
		if(l<=L&&R<=r){
			g[poi[p]].emplace_back(u,1);
			return;
		}
		int mid=(L+R)/2;
		if(l<=mid){
			link(l,r,u,p*2,L,mid);
		}
		if(r>mid){
			link(l,r,u,p*2+1,mid+1,R);
		}
	}
}seg;
void bfs(int s,int dis[N*5]){
	fill(dis+1,dis+tot+1,1e9);
	deque<int> q;
	dis[s]=0;
	q.push_back(s);
	while(q.size()){
		int u=q.front();
		q.pop_front();
		for(auto [v,w]:g[u]){
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!w) q.push_front(v);
				else q.push_back(v);
			}
		}
	}
}
vector<int> ins[N*2];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	tot=n;
	seg.init();
	For(i,1,n){
		cin>>L[i]>>R[i];
		seg.link(L[i],R[i],i);
	}
	bfs(1,disl);
	bfs(n,disr);
	For(i,1,n){
		int x=(disl[i]+disr[i]-(i>1&&i<n));
		if(x<1e9){
			ins[x].push_back(i);
		}
	}
	memset(dis,0x3f,sizeof(dis));
	deque<int> que;
	For(i,0,n*2){
		for(int u:ins[i]){
			if(dis[u]>i){
				dis[u]=i;
				que.push_back(u);
			}
		}
		while(que.size()&&dis[que.front()]<=i){
			int u=que.front();
			que.pop_front();
			for(auto [v,w]:g[u]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(!w) que.push_front(v);
					else que.push_back(v);
				}
			}
		}
	}
	cin>>q;
	For($,1,q){
		int x;
		cin>>x;
		cout<<(dis[x]<=1e9?dis[x]:-1)<<'\n';
	}
	return 0;
}

源文件, 语言: C++17

详细

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 9ms

memory: 40304kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 3ms

memory: 40584kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 361ms

memory: 89196kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 118ms

memory: 68480kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 78ms

memory: 63772kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 43ms

memory: 62000kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 51ms

memory: 67676kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 0ms

memory: 40368kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 3ms

memory: 40248kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 14ms

memory: 40388kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 14ms

memory: 40392kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 7ms

memory: 40544kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 3ms

memory: 40528kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 10ms

memory: 40600kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 12ms

memory: 40372kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 7ms

memory: 40432kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 7ms

memory: 40384kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 0ms

memory: 40332kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 7ms

memory: 40768kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 8ms

memory: 40736kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 7ms

memory: 41212kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 8ms

memory: 40940kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 3ms

memory: 40632kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 0ms

memory: 40724kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 7ms

memory: 40644kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 7ms

memory: 40696kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 6ms

memory: 40832kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 7ms

memory: 40772kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 12ms

memory: 40728kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 9ms

memory: 40664kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 3ms

memory: 40692kb

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: 7ms

memory: 40916kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 375ms

memory: 89312kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 148ms

memory: 68808kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 186ms

memory: 95776kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 176ms

memory: 95852kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 106ms

memory: 63912kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 122ms

memory: 70492kb

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 200000 lines

Test #39:

score: 0

Accepted

time: 50ms

memory: 51176kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 124ms

memory: 71768kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 188ms

memory: 78968kb

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 199636 lines

Extra Test:

score: 0

Extra Test Passed