QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#104766	#6334. Passport	________a____	100 ✓	1245ms	129784kb	C++14	2.4kb	2023-05-11 21:46:48	2023-05-11 21:46:51

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:46:51]
评测

测评结果：100
用时：1245ms
内存：129784kb

查看

[2023-05-11 21:46:48]
提交

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);
	e[u].push_back(w);
}
int id[MAXN];
void build(int l,int r,int p){
	data[p]=++N;
	if(l==r){
		id[l]=data[p];
		//add(l,data[p],1);
		return ;
	}
	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){
	if(x<=l&&r<=y) {
		//cout<<l<<' '<<r<<' '<<u<<endl;
		return add(data[p],u,0);
	}
	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[id[1]]=0;
	q.push_back(id[1]);
	vis[id[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[id[n]]=0;
	q.push_back(id[n]);
	vis[id[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(i,id[i],1);
		add(1,n,l,r,1,i);
	}
	int T;
	scanf("%d",&T);
	dij1(),dij2();
	dij();
	int x;
	while(T--){
		scanf("%d",&x);
		x=id[x];
		if(ans[x]>n) ans[x]=-1;
		printf("%d\n",ans[x]);
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 3ms

memory: 50568kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 11ms

memory: 50464kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 1052ms

memory: 123668kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 407ms

memory: 103484kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 274ms

memory: 100788kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 234ms

memory: 102708kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 176ms

memory: 100252kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 7ms

memory: 50580kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 8ms

memory: 50548kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 7ms

memory: 50548kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 7ms

memory: 50520kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 13ms

memory: 50524kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 14ms

memory: 50472kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 8ms

memory: 50588kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 8ms

memory: 50540kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 8ms

memory: 50648kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 8ms

memory: 50612kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 8ms

memory: 50624kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 30ms

memory: 51260kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 3ms

memory: 51248kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 18ms

memory: 51468kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 7ms

memory: 51488kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 17ms

memory: 51276kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 15ms

memory: 51236kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 4ms

memory: 51252kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 8ms

memory: 51196kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 12ms

memory: 51364kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 13ms

memory: 51400kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 20ms

memory: 51200kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 13ms

memory: 51180kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 14ms

memory: 51260kb

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

memory: 51256kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 1245ms

memory: 123828kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 463ms

memory: 103888kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 623ms

memory: 129072kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 563ms

memory: 129784kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 335ms

memory: 100852kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 447ms

memory: 107288kb

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

memory: 69744kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 438ms

memory: 107976kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 585ms

memory: 117016kb

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