#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e9 + 7;
const int N = 3e5 + 7;
struct SegmentExtractor{
vector < vector < int > > tree;
vector < int > vis;
int sz;
SegmentExtractor(int x){
sz = x+3;
tree.assign(4*sz , vector < int >{});
vis.assign(x+3 , 0);
}
void _add(int ind , int l , int r , int ql , int qr , int qind){
if(l >= ql and r <= qr){
tree[ind].push_back(qind);
return;
}
else if(l > qr or r < ql){
return;
}
int mid = (l+r)/2;
_add(ind*2 , l , mid , ql , qr , qind);
_add(ind*2+1, mid+1 , r , ql , qr , qind);
}
void add(int l , int r , int ind){
_add(1,1,sz,l,r,ind);
}
vector < int > ret;
void _extract(int ind , int l , int r , int p){
for(auto itr : tree[ind]){
ret.push_back(itr);
}
tree[ind].clear();
if(l != r){
int mid = (l+r)/2;
if(mid >= p)_extract(ind*2,l,mid,p);
else _extract(ind*2+1,mid+1,r,p);
}
}
vector < int > extract(int p){
ret.clear();
vector < int > newret;
_extract(1,1,sz,p);
for(auto itr : ret){
if(vis[itr] == 0){
newret.push_back(itr);
vis[itr] = 1;
}
}
return newret;
}
};
void solve(){
int n;
cin >> n;
pair < int , int > ran[N];
for(int i = 1;i<=n;i++){
cin >> ran[i].first >> ran[i].second;
}
int sp[2][N];
for(int i = 0;i<=n;i++){
sp[0][i] = sp[1][i] = inf;
}
//distance from 1
SegmentExtractor s1(N);
for(int i = 1;i<=n;i++){
s1.add(ran[i].first , ran[i].second , i);
}
vector < int > cs[N];
cs[0].push_back(1);
for(int i = 0;i<N;i++){
if(cs[i].size()){
for(auto itr : cs[i]){
sp[0][itr] = i;
vector < int > vtmp = s1.extract(itr);
for(auto itr1 : vtmp){
if(itr1 == itr)continue;
cs[i+1].push_back(itr1);
}
}
}
else break;
}
//distance from n
SegmentExtractor s2(N);
for(int i = 1;i<=n;i++){
s2.add(ran[i].first , ran[i].second , i);
cs[i].clear();
}
cs[0].clear();
cs[0].push_back(n);
for(int i = 0;i<N;i++){
if(cs[i].size()){
for(auto itr : cs[i]){
sp[1][itr] = i;
vector < int > vtmp = s2.extract(itr);
for(auto itr1 : vtmp){
if(itr1 == itr)continue;
cs[i+1].push_back(itr1);
}
}
}
else break;
}
//setting up to shortest path
// cout << "----------" << endl;
int ans[n+1];
for(int i = 0;i<=n;i++){
ans[i] = inf;
}
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;
SegmentExtractor s3(n);
for(int i = 1;i<=n;i++){
pq.push({sp[0][i] + sp[1][i] , i});
s3.add(ran[i].first , ran[i].second , i);
}
//doing the shortest path
while(pq.size()){
pair < int , int > tmp = pq.top();
pq.pop();
if(ans[tmp.second] > tmp.first){
ans[tmp.second] = tmp.first;
vector < int > v = s3.extract(tmp.second);
for(auto itr : v){
pq.push({tmp.first + 1 , itr});
}
}
}
//answering the queries
int q;
cin >> q;
while(q--){
int x;
cin >> x;
cout << ans[x] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
77904 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
77764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
77816 KB |
Output is correct |
| 2 |
Correct |
30 ms |
77908 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
77904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
77816 KB |
Output is correct |
| 2 |
Correct |
30 ms |
77908 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
77904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
77816 KB |
Output is correct |
| 2 |
Correct |
30 ms |
77908 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
77904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
77904 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
77764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
