#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 20, m = 450, INF = 1e9;
int Rcost[maxn];
pair<int,int> Lcost[maxn];
bool cmp(int a, int b) {
return Lcost[a].second < Lcost[b].second;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
pair<int,int> a[n+1];
vector<pair<int,int>> Lpos[m], Rpos[m];
vector<pair<int,int>> lpos[m], rpos[m];
for (int i=1;i<=n;i++) {
cin >> a[i].first >> a[i].second;
if (i!=1) {
Lpos[a[i].first/m].push_back({a[i].second, i});
lpos[a[i].first].push_back({a[i].second, i});
}
if (i!=n) {
Rpos[a[i].second/m].push_back({a[i].first, i});
rpos[a[i].second].push_back({a[i].first, i});
}
}
for (int i=0;i<m;i++) sort(Rpos[i].rbegin(), Rpos[i].rend());
for (int i=1;i<=n;i++) sort(rpos[i].rbegin(), rpos[i].rend());
bool vis[n+1];
for (int i=1;i<=n;i++) vis[i] = false;
vis[n] = true;
vector<int> from = {n}, to;
int Rcost[n+1];
for (int i=1;i<=n;i++) Rcost[i] = INF;
for (int cost=-1; from.size()>0; cost++) {
for (int u:from) Rcost[u] = max(cost, (int)0);
for (int u:from) {
for (int R=m-1;R*m>=u;R--) {
while (Rpos[R].size()>0 && Rpos[R].back().first<=u) {
int v = Rpos[R].back().second;
if (!vis[v]) to.push_back(v);
vis[v] = true;
Rpos[R].pop_back();
}
}
int r = (u+m-1)/m*m - 1;
for (;r>=u;r--) {
while (rpos[r].size()>0 && rpos[r].back().first<=u) {
int v = rpos[r].back().second;
if (!vis[v]) to.push_back(v);
vis[v] = true;
rpos[r].pop_back();
}
}
}
from.clear();
swap(to, from);
}
for (int i=0;i<m;i++) sort(Lpos[i].begin(), Lpos[i].end());
for (int i=0;i<=n;i++) sort(lpos[i].begin(), lpos[i].end());
for (int i=1;i<=n;i++) vis[i] = false;
vis[1] = true;
from = {1};
for (int i=1;i<=n;i++) Lcost[i] = {INF, INF};
Lcost[1].second = Rcost[1] + 1;
for (int cost=0; from.size()>0; cost++) {
sort(from.begin(), from.end(), cmp);
for (int u:from) Lcost[u].first = cost;
for (int u:from) {
for (int L=0;(L+1)*m-1<=u;L++) {
while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
int v = Lpos[L].back().second;
if (!vis[v]) {
to.push_back(v);
Lcost[v].second = min(Rcost[v], Lcost[u].second);
}
vis[v] = true;
Lpos[L].pop_back();
}
}
int l = u/m*m;
for (;l<=u;l++) {
while (lpos[l].size()>0 && lpos[l].back().first>=u) {
int v = lpos[l].back().second;
if (!vis[v]) {
to.push_back(v);
Lcost[v].second = min(Rcost[v], Lcost[u].second);
}
vis[v] = true;
lpos[l].pop_back();
}
}
}
from.clear();
swap(to, from);
}
int q;
cin >> q;
for (int i=0;i<q;i++) {
int pos;
cin >> pos;
if (Lcost[pos].first>=INF || Lcost[pos].second>=INF) cout << "-1\n";
else cout << Lcost[pos].first + Lcost[pos].second << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
6 ms |
6848 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
6 ms |
6848 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
