#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 2e5 + 5;
const int inf = 1e9;
int pos[NM], n, ans[NM];
vector<pair<int, int>> g[4 * NM];
void build(int x = 1, int l = 1, int r = n)
{
if (l == r)
{
pos[l] = x;
return;
}
int m = l + r >> 1;
build(x << 1, l, m);
build(x << 1 | 1, m + 1, r);
g[x << 1].emplace_back(x, 0);
g[x << 1 | 1].emplace_back(x, 0);
// cout << (x << 1) << ' ' << x << ' ' << 0 << endl;
// cout << (x << 1 | 1) << ' ' << x << ' ' << 0 << endl;
}
void upd(int t, int l, int r, int x = 1, int lx = 1, int rx = n)
{
if (l > rx || lx > r)
return;
if (lx >= l && rx <= r)
{
g[x].emplace_back(t, 1);
// cout << x << ' ' << t << ' ' << 1 << endl;
return;
}
int m = lx + rx >> 1;
upd(t, l, r, x << 1, lx, m);
upd(t, l, r, x << 1 | 1, m + 1, rx);
}
pair<int, int> a[NM];
vector<int> bfs(int s)
{
vector<int> dist(4 * n + 1, inf);
deque<pair<int, int>> dq;
for (int i = 1; i <= n; i++)
{
if (a[i].fi == 1 && a[i].se == n)
{
dist[pos[i]] = 1;
dq.push_front({1, pos[i]});
}
}
dist[s] = 0;
dq.push_front({0, s});
while (!dq.empty())
{
auto u = dq.front();
dq.pop_front();
if (u.fi != dist[u.se])
continue;
for (auto v : g[u.se])
if (dist[v.fi] > u.fi + v.se)
{
dist[v.fi] = u.fi + v.se;
if (v.se)
dq.push_back({dist[v.fi], v.fi});
else
dq.push_front({dist[v.fi], v.fi});
}
}
return dist;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
void solve()
{
cin >> n;
build();
for (int i = 1; i <= n; i++)
{
cin >> a[i].fi >> a[i].se;
upd(pos[i], a[i].fi, a[i].se);
}
vector<int> dist1 = bfs(pos[1]), dist2 = bfs(pos[n]);
vector<int> dist(4 * n + 1);
for (int i = 1; i < dist.size(); i++)
{
dist[i] = dist1[i] + dist2[i] - 1;
if (i == pos[1])
dist[i] = dist2[i];
if (i == pos[n])
dist[i] = dist1[i];
if (dist[i] < inf)
pq.push({dist[i], i});
}
for (int i = 1; i <= n; i++)
if (a[i].fi == 1 && a[i].se == n)
{
dist[pos[i]] = 1;
pq.push({1, pos[i]});
}
while (!pq.empty())
{
auto u = pq.top();
pq.pop();
if (u.fi != dist[u.se])
continue;
for (auto v : g[u.se])
if (dist[v.fi] > u.fi + v.se)
{
dist[v.fi] = u.fi + v.se;
pq.push({dist[v.fi], v.fi});
}
}
for (int i = 1; i <= n; i++)
ans[i] = (dist[pos[i]] < inf ? dist[pos[i]] : -1);
int q; cin >> q;
while (q--)
{
int x;
cin >> x;
cout << ans[x] << endl;
}
}
signed main()
{
fastIO
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
int tc = 1; // cin >> tc;
while (tc--)
solve();
}
Compilation message
passport.cpp: In function 'void build(long long int, long long int, long long int)':
passport.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int m = l + r >> 1;
| ~~^~~
passport.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
passport.cpp:50:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int m = lx + rx >> 1;
| ~~~^~~~
passport.cpp: In function 'void solve()':
passport.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 1; i < dist.size(); i++)
| ~~^~~~~~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
