This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,q,l[800005],r[800005],dl[800005],dr[800005],dis[800005],idx[200005];
vector<int> g[800005];
void bfs(int* d)
{
set<pair<int,int>> st;
for(int i=1;i<=n;i++) st.emplace(d[i],i);
while(!st.empty())
{
auto it=st.begin();
int x=it->second;
st.erase(it);
if(x<=n)
{
for(int y=idx[x];y>=1;y/=2)
{
if(d[n+y]>d[x])
{
if(st.find({d[n+y],n+y})!=st.end()) st.erase(st.find({d[n+y],n+y}));
d[n+y]=d[x];st.emplace(d[n+y],n+y);
}
}
}
else
{
for(int y:g[x])
{
int f=d[x]+(y<=n);
if(d[y]>f)
{
if(st.find({d[y],y})!=st.end()) st.erase(st.find({d[y],y}));
d[y]=f;st.emplace(f,y);
}
}
}
}
}
void build(int v,int l,int r)
{
if(l==r) {idx[l]=v;return;}
int mid=l+r>>1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
}
void add(int v,int l,int r,int ql,int qr,int i)
{
if(l>r||l>qr||r<ql) return;
if(ql<=l&&r<=qr)
{
g[i].push_back(n+v);
g[n+v].push_back(i);
return;
}
int mid=l+r>>1;
add(v*2,l,mid,ql,qr,i);
add(v*2+1,mid+1,r,ql,qr,i);
}
signed main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
build(1,1,n);
for(int i=1;i<=n;i++) add(1,1,n,l[i],r[i],i);
for(int i=1;i<=800000;i++) dl[i]=dr[i]=dis[i]=inf;
dl[1]=0;dr[n]=0;
bfs(dl);bfs(dr);
dl[1]=1;dr[n]=1;
for(int i=1;i<=n;i++) dis[i]=dl[i]+dr[i];
bfs(dis);
for(int i=1;i<=n;i++) if(dis[i]>=inf) dis[i]=-1; else dis[i]--;
scanf("%d",&q);
while(q--)
{
int x;scanf("%d",&x);
printf("%d\n",dis[x]);
}
}
Compilation message (stderr)
passport.cpp: In function 'void build(int, int, int)':
passport.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid=l+r>>1;
| ~^~
passport.cpp: In function 'void add(int, int, int, int, int, int)':
passport.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid=l+r>>1;
| ~^~
passport.cpp: In function 'int main()':
passport.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
passport.cpp:67:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
passport.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
passport.cpp:80:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | int x;scanf("%d",&x);
| ~~~~~^~~~~~~~~
# | 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... |