#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> prze;
vector<pair<int, int>> graph[2*524300];
int odl[2*524300];
int sumk[2*524300];
int n;
void dodajp(int l, int r, int curl, int curr, int cur, int jaki)
{
if(l > curr || r < curl)
{
return;
}
else if(l <= curl && curr <= r)
{
graph[cur].push_back({262143 + jaki, 1});
}
else
{
dodajp(l, r, curl, (curl + curr) / 2, 2 * cur, jaki);
dodajp(l, r, (curl + curr) / 2 + 1, curr, 2 * cur + 1, jaki);
}
}
void djikstra(int skad)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
odl[skad] = 0;
pq.push({0, skad});
for(int i = 1; i <= n; i++)
{
if(prze[i].first + 262143 <= skad && skad <= prze[i].second + 262143)
{
if(odl[262143 + i] > 0)
{
odl[262143 + i] = 0;
pq.push({0, 262143 + i});
}
}
}
while(!pq.empty())
{
auto x = pq.top();
pq.pop();
if(odl[x.second] >= x.first)
{
for(auto t : graph[x.second])
{
if(odl[t.first] > x.first + t.second)
{
odl[t.first] = x.first + t.second;
pq.push({odl[t.first], t.first});
}
}
}
}
}
int main()
{
cin >> n;
for(int i = 2; i <= 524250; i++)
{
graph[i].push_back({i / 2, 0});
}
prze.push_back({0, 0});
for(int i = 1; i <= n; i++)
{
int l, r;
cin >> l >> r;
prze.push_back({l, r});
dodajp(l, r, 1, 262144, 1, i);
}
for(int i = 0; i < 524290; i++)
{
odl[i] = 10000000;
}
djikstra(262144);
for(int i = 0; i < 524290; i++)
{
sumk[i] += odl[i];
odl[i] = 10000000;
}
djikstra(262143 + n);
for(int i = 0; i < 524290; i++)
{
sumk[i] += odl[i];
odl[i] = 10000000;
}
for(int i = 262144; i < 262144 + n; i++)
{
graph[0].push_back({i, min(sumk[i], 10000000)});
}
djikstra(0);
int q;
cin >> q;
while(q--)
{
int x;
cin >> x;
if(odl[262143 + x] >= 10000000)
{
cout << -1 << endl;
}
else
{
cout << odl[262143 + x] + 1 << endl;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |