#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 5e5 + 10;
struct graph
{
vector < pair < int, int > > adj[maxn * 5];
int dist[maxn * 5], lf[maxn * 5], rf[maxn * 5];
int fict, root, n;
graph() {};
int build(int left, int right)
{
///cout << left << " :: " << right << " " << fict << endl;
if (left == right)
return left;
int mid = (left + right) / 2;
int left_child = build(left, mid);
int right_child = build(mid + 1, right);
int ver = ++ fict;
adj[left_child].push_back({ver, 0});
adj[right_child].push_back({ver, 0});
//cout << left_child << " " << ver << " " << 0 << endl;
//cout << right_child << " " << ver << " " << 0 << endl;
lf[ver] = left_child;
rf[ver] = right_child;
return ver;
}
graph(int _n)
{
n = _n;
fict = n;
root = build(1, n);
}
void range_update(int node, int l, int r, int ql, int qr, int v)
{
if (l > qr || r < ql)
return;
if (l >= ql && r <= qr)
{
adj[node].push_back({v, 1});
///cout << "make edge " << node << " " << l << " " << r << " " << v << endl;
///cout << node << " " << v << " " << 1 << endl;
return;
}
int m = (l + r) / 2;
range_update(lf[node], l, m, ql, qr, v);
range_update(rf[node], m + 1, r, ql, qr, v);
}
void add_range_edge(int l, int r, int v)
{
range_update(root, 1, n, l, r, v);
}
void add_edge(int v, int u, int w)
{
adj[v].push_back({u, w});
///adj[u].push_back({v, w});
}
void bfs(int st)
{
for (int i = 1; i <= fict; i ++)
{
dist[i] = 1e9;
}
deque < int > q;
dist[st] = 0;
q.push_back(st);
while(!q.empty())
{
int v = q.front();
q.pop_front();
///cout << "here " << v << " " << dist[v] << endl;
for (pair < int, int > nb : adj[v])
{
if (dist[nb.first] > dist[v] + nb.second)
{
dist[nb.first] = dist[v] + nb.second;
if (nb.second == 0)
q.push_front(nb.first);
else
q.push_back(nb.first);
}
}
}
}
};
int n, q, l[maxn], r[maxn];
int a[maxn], b[maxn];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> l[i] >> r[i];
}
graph st(n + 1);
for (int i = 1; i <= n; i ++)
{
st.add_range_edge(l[i], r[i], i);
///for (int j = l[i]; j <= r[i]; j ++)
///st.add_edge(j, i, 1);
///cout << j << " " << i << " " << 1 << endl;
}
st.bfs(1);
for (int i = 1; i <= n; i ++)
a[i] = st.dist[i];
st.bfs(n);
for (int i = 1; i <= n; i ++)
b[i] = st.dist[i];
/**for (int i = 1; i <= n; i ++)
cout << b[i] << " ";
cout << endl;
return;*/
///cout << "------------" << endl;
for (int i = 1; i <= n; i ++)
{
int edge = a[i] + b[i];
if (a[i] > 0 && b[i] > 0)
edge --;
st.add_edge(n + 1, i, edge);
///cout << n + 1 << " " << i << " " << a[i] << " " << b[i] << endl;
}
st.bfs(n + 1);
/**for (int i = 1; i <= n; i ++)
cout << st.dist[i] << " ";
cout << endl;*/
cin >> q;
for (int i = 1; i <= q; i ++)
{
int x;
cin >> x;
int ans = st.dist[x];
if (ans > n)
cout << -1 << endl;
else
cout << ans << endl;
}
}
int main()
{
///speed();
freopen("text.txt", "r", stdin);
solve();
return 0;
}
/**
9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6
*/
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:169:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | freopen("text.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
88276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
88252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
88252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
88252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
88276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
