#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,pos[200001],dis[3][1<<20];
bool vis[3][1<<20],leaf[1<<20];
vector<pii> adj[1<<20];
void build(int idx, int l, int r) {
if (l==r) {
pos[l]=idx;
leaf[idx]=true;
} else {
adj[2*idx].push_back(pii(idx,0));
adj[2*idx+1].push_back(pii(idx,0));
int mid=(l+r)/2;
build(2*idx,l,mid);
build(2*idx+1,mid+1,r);
}
}
void add(int l, int r, int idx, int x, int y, int i) {
if (x>r || y<l) return;
if (x<=l && r<=y) {
adj[idx].push_back({pos[i],1});
} else {
int mid=(l+r)/2;
add(l,mid,2*idx,x,y,i);
add(mid+1,r,2*idx+1,x,y,i);
}
}
priority_queue<pii, vector<pii>, greater<pii>> q;
void dij(int x) {
while (!q.empty()) {
int node=q.top().second;
q.pop();
if (vis[x][node]) continue;
vis[x][node]=true;
for (auto s : adj[node]) {
if (dis[x][s.first]>dis[x][node]+s.second) {
dis[x][s.first]=dis[x][node]+s.second;
q.push({dis[x][s.first],s.first});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for (int i=0; i<(1<<20); ++i) dis[0][i]=dis[1][i]=dis[2][i]=1e9;
cin>>n;
build(1,1,n);
for (int i=1; i<=n; ++i) {
int l,r; cin>>l>>r;
add(1,n,1,l,r,i);
}
dis[0][pos[1]]=0;
q.push({0,pos[1]});
dij(0);
dis[1][pos[n]]=0;
q.push({0,pos[n]});
dij(1);
for (int i=1; i<=4*n; ++i) {
if (i==pos[1] || i==pos[n]) dis[2][i]=dis[0][i]+dis[1][i];
else dis[2][i]=dis[0][i]+dis[1][i]-leaf[i];
q.push({dis[2][i],i});
}
dij(2);
int q; cin>>q;
while (q--) {
int x; cin>>x;
if (dis[2][pos[x]]>=1e9) cout<<-1<<"\n";
else cout<<dis[2][pos[x]]<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
37232 KB |
Output is correct |
2 |
Correct |
21 ms |
37196 KB |
Output is correct |
3 |
Correct |
19 ms |
37204 KB |
Output is correct |
4 |
Correct |
781 ms |
89064 KB |
Output is correct |
5 |
Correct |
392 ms |
69120 KB |
Output is correct |
6 |
Correct |
251 ms |
63764 KB |
Output is correct |
7 |
Correct |
284 ms |
61852 KB |
Output is correct |
8 |
Correct |
239 ms |
68844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37164 KB |
Output is correct |
2 |
Correct |
19 ms |
37204 KB |
Output is correct |
3 |
Correct |
20 ms |
37204 KB |
Output is correct |
4 |
Correct |
22 ms |
37184 KB |
Output is correct |
5 |
Correct |
21 ms |
37192 KB |
Output is correct |
6 |
Correct |
20 ms |
37204 KB |
Output is correct |
7 |
Correct |
20 ms |
37288 KB |
Output is correct |
8 |
Correct |
20 ms |
37212 KB |
Output is correct |
9 |
Correct |
19 ms |
37204 KB |
Output is correct |
10 |
Correct |
22 ms |
37200 KB |
Output is correct |
11 |
Correct |
21 ms |
37292 KB |
Output is correct |
12 |
Correct |
21 ms |
37304 KB |
Output is correct |
13 |
Correct |
20 ms |
37336 KB |
Output is correct |
14 |
Correct |
20 ms |
37276 KB |
Output is correct |
15 |
Correct |
21 ms |
37332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37164 KB |
Output is correct |
2 |
Correct |
19 ms |
37204 KB |
Output is correct |
3 |
Correct |
20 ms |
37204 KB |
Output is correct |
4 |
Correct |
22 ms |
37184 KB |
Output is correct |
5 |
Correct |
21 ms |
37192 KB |
Output is correct |
6 |
Correct |
20 ms |
37204 KB |
Output is correct |
7 |
Correct |
20 ms |
37288 KB |
Output is correct |
8 |
Correct |
20 ms |
37212 KB |
Output is correct |
9 |
Correct |
19 ms |
37204 KB |
Output is correct |
10 |
Correct |
22 ms |
37200 KB |
Output is correct |
11 |
Correct |
21 ms |
37292 KB |
Output is correct |
12 |
Correct |
21 ms |
37304 KB |
Output is correct |
13 |
Correct |
20 ms |
37336 KB |
Output is correct |
14 |
Correct |
20 ms |
37276 KB |
Output is correct |
15 |
Correct |
21 ms |
37332 KB |
Output is correct |
16 |
Correct |
24 ms |
37844 KB |
Output is correct |
17 |
Correct |
24 ms |
37772 KB |
Output is correct |
18 |
Correct |
24 ms |
37948 KB |
Output is correct |
19 |
Correct |
25 ms |
38024 KB |
Output is correct |
20 |
Correct |
23 ms |
37716 KB |
Output is correct |
21 |
Correct |
25 ms |
37776 KB |
Output is correct |
22 |
Correct |
22 ms |
37716 KB |
Output is correct |
23 |
Correct |
23 ms |
37744 KB |
Output is correct |
24 |
Correct |
23 ms |
37876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37164 KB |
Output is correct |
2 |
Correct |
19 ms |
37204 KB |
Output is correct |
3 |
Correct |
20 ms |
37204 KB |
Output is correct |
4 |
Correct |
22 ms |
37184 KB |
Output is correct |
5 |
Correct |
21 ms |
37192 KB |
Output is correct |
6 |
Correct |
20 ms |
37204 KB |
Output is correct |
7 |
Correct |
20 ms |
37288 KB |
Output is correct |
8 |
Correct |
20 ms |
37212 KB |
Output is correct |
9 |
Correct |
19 ms |
37204 KB |
Output is correct |
10 |
Correct |
22 ms |
37200 KB |
Output is correct |
11 |
Correct |
21 ms |
37292 KB |
Output is correct |
12 |
Correct |
21 ms |
37304 KB |
Output is correct |
13 |
Correct |
20 ms |
37336 KB |
Output is correct |
14 |
Correct |
20 ms |
37276 KB |
Output is correct |
15 |
Correct |
21 ms |
37332 KB |
Output is correct |
16 |
Correct |
24 ms |
37844 KB |
Output is correct |
17 |
Correct |
24 ms |
37772 KB |
Output is correct |
18 |
Correct |
24 ms |
37948 KB |
Output is correct |
19 |
Correct |
25 ms |
38024 KB |
Output is correct |
20 |
Correct |
23 ms |
37716 KB |
Output is correct |
21 |
Correct |
25 ms |
37776 KB |
Output is correct |
22 |
Correct |
22 ms |
37716 KB |
Output is correct |
23 |
Correct |
23 ms |
37744 KB |
Output is correct |
24 |
Correct |
23 ms |
37876 KB |
Output is correct |
25 |
Correct |
19 ms |
37264 KB |
Output is correct |
26 |
Correct |
18 ms |
37204 KB |
Output is correct |
27 |
Correct |
25 ms |
37872 KB |
Output is correct |
28 |
Correct |
23 ms |
37716 KB |
Output is correct |
29 |
Correct |
23 ms |
37724 KB |
Output is correct |
30 |
Correct |
23 ms |
37768 KB |
Output is correct |
31 |
Correct |
26 ms |
37768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
37232 KB |
Output is correct |
2 |
Correct |
21 ms |
37196 KB |
Output is correct |
3 |
Correct |
19 ms |
37204 KB |
Output is correct |
4 |
Correct |
781 ms |
89064 KB |
Output is correct |
5 |
Correct |
392 ms |
69120 KB |
Output is correct |
6 |
Correct |
251 ms |
63764 KB |
Output is correct |
7 |
Correct |
284 ms |
61852 KB |
Output is correct |
8 |
Correct |
239 ms |
68844 KB |
Output is correct |
9 |
Correct |
20 ms |
37164 KB |
Output is correct |
10 |
Correct |
19 ms |
37204 KB |
Output is correct |
11 |
Correct |
20 ms |
37204 KB |
Output is correct |
12 |
Correct |
22 ms |
37184 KB |
Output is correct |
13 |
Correct |
21 ms |
37192 KB |
Output is correct |
14 |
Correct |
20 ms |
37204 KB |
Output is correct |
15 |
Correct |
20 ms |
37288 KB |
Output is correct |
16 |
Correct |
20 ms |
37212 KB |
Output is correct |
17 |
Correct |
19 ms |
37204 KB |
Output is correct |
18 |
Correct |
22 ms |
37200 KB |
Output is correct |
19 |
Correct |
21 ms |
37292 KB |
Output is correct |
20 |
Correct |
21 ms |
37304 KB |
Output is correct |
21 |
Correct |
20 ms |
37336 KB |
Output is correct |
22 |
Correct |
20 ms |
37276 KB |
Output is correct |
23 |
Correct |
21 ms |
37332 KB |
Output is correct |
24 |
Correct |
24 ms |
37844 KB |
Output is correct |
25 |
Correct |
24 ms |
37772 KB |
Output is correct |
26 |
Correct |
24 ms |
37948 KB |
Output is correct |
27 |
Correct |
25 ms |
38024 KB |
Output is correct |
28 |
Correct |
23 ms |
37716 KB |
Output is correct |
29 |
Correct |
25 ms |
37776 KB |
Output is correct |
30 |
Correct |
22 ms |
37716 KB |
Output is correct |
31 |
Correct |
23 ms |
37744 KB |
Output is correct |
32 |
Correct |
23 ms |
37876 KB |
Output is correct |
33 |
Correct |
19 ms |
37264 KB |
Output is correct |
34 |
Correct |
18 ms |
37204 KB |
Output is correct |
35 |
Correct |
25 ms |
37872 KB |
Output is correct |
36 |
Correct |
23 ms |
37716 KB |
Output is correct |
37 |
Correct |
23 ms |
37724 KB |
Output is correct |
38 |
Correct |
23 ms |
37768 KB |
Output is correct |
39 |
Correct |
26 ms |
37768 KB |
Output is correct |
40 |
Correct |
837 ms |
89412 KB |
Output is correct |
41 |
Correct |
415 ms |
69640 KB |
Output is correct |
42 |
Correct |
523 ms |
96648 KB |
Output is correct |
43 |
Correct |
526 ms |
96448 KB |
Output is correct |
44 |
Correct |
278 ms |
64224 KB |
Output is correct |
45 |
Correct |
368 ms |
71484 KB |
Output is correct |
46 |
Correct |
179 ms |
50364 KB |
Output is correct |
47 |
Correct |
494 ms |
72072 KB |
Output is correct |
48 |
Correct |
441 ms |
79972 KB |
Output is correct |