#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
int N, Q;
pii A[MAXN+10];
vector<int> adj[MAXN+10];
int init(int node, int tl, int tr)
{
if(tl==tr) return tl;
int mid=tl+tr>>1;
adj[init(node*2, tl, mid)].push_back(node+N);
adj[init(node*2+1, mid+1, tr)].push_back(node+N);
return node+N;
}
void query(int node, int tl, int tr, int l, int r, int k)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
if(tl==tr) adj[tl].push_back(k);
else adj[node+N].push_back(k);
return;
}
int mid=tl+tr>>1;
query(node*2, tl, mid, l, r, k);
query(node*2+1, mid+1, tr, l, r, k);
}
int D1[MAXN+10], D2[MAXN+10], D3[MAXN+10];
void bfs(int *D)
{
deque<pii> Q;
vector<pii> V;
for(int i=1; i<=N; i++) if(D[i]) V.push_back({D[i], i});
sort(V.begin(), V.end());
for(int p=0; p<V.size();)
{
Q.push_back({V[p].second, V[p].first}); p++;
while(!Q.empty())
{
pii t=Q.front(); Q.pop_front();
if(D[t.first]!=t.second) continue;
int now=t.first;
for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push_back({V[p].second, V[p].first});
for(auto nxt : adj[now])
{
if(D[nxt]!=0 && D[nxt]<=D[now]+1) continue;
if(nxt<=N)
{
D[nxt]=D[now]+1;
Q.push_back({nxt, D[nxt]});
}
else
{
D[nxt]=D[now];
Q.push_front({nxt, D[nxt]});
}
}
}
}
for(int i=1; i<=N; i++) if(!D[i]) D[i]=N+N;
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
init(1, 1, N);
for(int i=1; i<=N; i++)
{
auto [l, r]=A[i];
query(1, 1, N, l, r, i);
}
for(int i=1; i<=N; i++) if(A[i].first==1) D1[i]=1;
bfs(D1);
for(int i=1; i<=N; i++) if(A[i].second==N) D2[i]=1;
bfs(D2);
for(int i=1; i<=N; i++) D3[i]=D1[i]+D2[i]-1;
bfs(D3);
scanf("%d", &Q);
while(Q--)
{
int t;
scanf("%d", &t);
if(D3[t]>N) D3[t]=-1;
printf("%d\n", D3[t]);
}
}
Compilation message
passport.cpp: In function 'int init(int, int, int)':
passport.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | int mid=tl+tr>>1;
| ~~^~~
passport.cpp: In function 'void query(int, int, int, int, int, int)':
passport.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid=tl+tr>>1;
| ~~^~~
passport.cpp: In function 'void bfs(int*)':
passport.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int p=0; p<V.size();)
| ~^~~~~~~~~
passport.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push_back({V[p].second, V[p].first});
| ~^~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
passport.cpp:77:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
passport.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
14 ms |
23796 KB |
Output is correct |
3 |
Correct |
13 ms |
23764 KB |
Output is correct |
4 |
Correct |
443 ms |
59476 KB |
Output is correct |
5 |
Correct |
211 ms |
48228 KB |
Output is correct |
6 |
Correct |
146 ms |
46624 KB |
Output is correct |
7 |
Correct |
124 ms |
47308 KB |
Output is correct |
8 |
Correct |
115 ms |
46876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23796 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23816 KB |
Output is correct |
4 |
Correct |
13 ms |
23800 KB |
Output is correct |
5 |
Correct |
12 ms |
23708 KB |
Output is correct |
6 |
Correct |
12 ms |
23704 KB |
Output is correct |
7 |
Correct |
12 ms |
23804 KB |
Output is correct |
8 |
Correct |
12 ms |
23700 KB |
Output is correct |
9 |
Correct |
13 ms |
23804 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
15 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
12 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23764 KB |
Output is correct |
15 |
Correct |
16 ms |
23816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23796 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23816 KB |
Output is correct |
4 |
Correct |
13 ms |
23800 KB |
Output is correct |
5 |
Correct |
12 ms |
23708 KB |
Output is correct |
6 |
Correct |
12 ms |
23704 KB |
Output is correct |
7 |
Correct |
12 ms |
23804 KB |
Output is correct |
8 |
Correct |
12 ms |
23700 KB |
Output is correct |
9 |
Correct |
13 ms |
23804 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
15 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
12 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23764 KB |
Output is correct |
15 |
Correct |
16 ms |
23816 KB |
Output is correct |
16 |
Correct |
15 ms |
24172 KB |
Output is correct |
17 |
Correct |
15 ms |
24148 KB |
Output is correct |
18 |
Correct |
15 ms |
24276 KB |
Output is correct |
19 |
Correct |
16 ms |
24276 KB |
Output is correct |
20 |
Correct |
14 ms |
24096 KB |
Output is correct |
21 |
Correct |
14 ms |
24128 KB |
Output is correct |
22 |
Correct |
14 ms |
24048 KB |
Output is correct |
23 |
Correct |
15 ms |
24104 KB |
Output is correct |
24 |
Correct |
14 ms |
24148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23796 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23816 KB |
Output is correct |
4 |
Correct |
13 ms |
23800 KB |
Output is correct |
5 |
Correct |
12 ms |
23708 KB |
Output is correct |
6 |
Correct |
12 ms |
23704 KB |
Output is correct |
7 |
Correct |
12 ms |
23804 KB |
Output is correct |
8 |
Correct |
12 ms |
23700 KB |
Output is correct |
9 |
Correct |
13 ms |
23804 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
15 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
12 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23764 KB |
Output is correct |
15 |
Correct |
16 ms |
23816 KB |
Output is correct |
16 |
Correct |
15 ms |
24172 KB |
Output is correct |
17 |
Correct |
15 ms |
24148 KB |
Output is correct |
18 |
Correct |
15 ms |
24276 KB |
Output is correct |
19 |
Correct |
16 ms |
24276 KB |
Output is correct |
20 |
Correct |
14 ms |
24096 KB |
Output is correct |
21 |
Correct |
14 ms |
24128 KB |
Output is correct |
22 |
Correct |
14 ms |
24048 KB |
Output is correct |
23 |
Correct |
15 ms |
24104 KB |
Output is correct |
24 |
Correct |
14 ms |
24148 KB |
Output is correct |
25 |
Correct |
12 ms |
23764 KB |
Output is correct |
26 |
Correct |
15 ms |
23788 KB |
Output is correct |
27 |
Correct |
16 ms |
24192 KB |
Output is correct |
28 |
Correct |
15 ms |
24148 KB |
Output is correct |
29 |
Correct |
16 ms |
24080 KB |
Output is correct |
30 |
Correct |
16 ms |
24040 KB |
Output is correct |
31 |
Correct |
15 ms |
24116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
14 ms |
23796 KB |
Output is correct |
3 |
Correct |
13 ms |
23764 KB |
Output is correct |
4 |
Correct |
443 ms |
59476 KB |
Output is correct |
5 |
Correct |
211 ms |
48228 KB |
Output is correct |
6 |
Correct |
146 ms |
46624 KB |
Output is correct |
7 |
Correct |
124 ms |
47308 KB |
Output is correct |
8 |
Correct |
115 ms |
46876 KB |
Output is correct |
9 |
Correct |
13 ms |
23796 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
13 ms |
23816 KB |
Output is correct |
12 |
Correct |
13 ms |
23800 KB |
Output is correct |
13 |
Correct |
12 ms |
23708 KB |
Output is correct |
14 |
Correct |
12 ms |
23704 KB |
Output is correct |
15 |
Correct |
12 ms |
23804 KB |
Output is correct |
16 |
Correct |
12 ms |
23700 KB |
Output is correct |
17 |
Correct |
13 ms |
23804 KB |
Output is correct |
18 |
Correct |
12 ms |
23764 KB |
Output is correct |
19 |
Correct |
15 ms |
23764 KB |
Output is correct |
20 |
Correct |
14 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23756 KB |
Output is correct |
22 |
Correct |
15 ms |
23764 KB |
Output is correct |
23 |
Correct |
16 ms |
23816 KB |
Output is correct |
24 |
Correct |
15 ms |
24172 KB |
Output is correct |
25 |
Correct |
15 ms |
24148 KB |
Output is correct |
26 |
Correct |
15 ms |
24276 KB |
Output is correct |
27 |
Correct |
16 ms |
24276 KB |
Output is correct |
28 |
Correct |
14 ms |
24096 KB |
Output is correct |
29 |
Correct |
14 ms |
24128 KB |
Output is correct |
30 |
Correct |
14 ms |
24048 KB |
Output is correct |
31 |
Correct |
15 ms |
24104 KB |
Output is correct |
32 |
Correct |
14 ms |
24148 KB |
Output is correct |
33 |
Correct |
12 ms |
23764 KB |
Output is correct |
34 |
Correct |
15 ms |
23788 KB |
Output is correct |
35 |
Correct |
16 ms |
24192 KB |
Output is correct |
36 |
Correct |
15 ms |
24148 KB |
Output is correct |
37 |
Correct |
16 ms |
24080 KB |
Output is correct |
38 |
Correct |
16 ms |
24040 KB |
Output is correct |
39 |
Correct |
15 ms |
24116 KB |
Output is correct |
40 |
Correct |
514 ms |
60148 KB |
Output is correct |
41 |
Correct |
253 ms |
48412 KB |
Output is correct |
42 |
Correct |
316 ms |
61584 KB |
Output is correct |
43 |
Correct |
305 ms |
62324 KB |
Output is correct |
44 |
Correct |
186 ms |
46488 KB |
Output is correct |
45 |
Correct |
230 ms |
48480 KB |
Output is correct |
46 |
Correct |
94 ms |
33516 KB |
Output is correct |
47 |
Correct |
245 ms |
50708 KB |
Output is correct |
48 |
Correct |
283 ms |
53764 KB |
Output is correct |