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 long long MX=2e5+10;
const long long INF=1e9;
pair < int , int > tree[4*MX];
void upd(int v,int tl,int tr,int in,pair < int , int > zn)
{
if(tl==tr)
{
tree[v]=min(tree[v],zn);
return;
}
int mid=(tl+tr)/2;
if(in<=mid)
{
upd(v*2,tl,mid,in,zn);
}
else
{
upd(v*2+1,mid+1,tr,in,zn);
}
tree[v]=min(tree[v*2],tree[v*2+1]);
}
pair < int , int > fget(int v,int tl,int tr,int l,int r)
{
if(r<tl || tr<l)
{
return make_pair(INF,0);
}
if(l<=tl && tr<=r)
{
return tree[v];
}
int mid=(tl+tr)/2;
return min(fget(v*2,tl,mid,l,r),fget(v*2+1,mid+1,tr,l,r));
}
int l[MX],r[MX];
int n,k;
void compr()
{
map < int , int > mp;
for(int i=1;i<=n;i++)
{
mp[l[i]]=1;
mp[r[i]]=1;
}
int uk=0;
for(auto & u:mp)
{
uk++;
u.second=uk;
}
for(int i=1;i<=n;i++)
{
l[i]=mp[l[i]];
r[i]=mp[r[i]];
}
}
int lca[20][MX];
void fun(int a,int b)
{
if(a==b)
{
cout<<"0\n";
return;
}
if(l[b]<=r[a] && r[a]<=r[b])
{
cout<<"1\n";
return;
}
if(r[b]<r[a] || r[a]<l[lca[19][b]])
{
cout<<"imposible\n";
return;
}
int ans=2;
for(int i=19;i>=0;i--)
{
if(r[a]<l[lca[i][b]])
{
b=lca[i][b];
ans+=(1<<i);
}
}
cout<<ans<<"\n";
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>l[i]>>r[i];
}
compr();
fill(tree+1,tree+4*MX,make_pair(INF,0));
for(int i=1;i<=n;i++)
{
upd(1,1,2*n,r[i],make_pair(l[i],i));
}
for(int i=1;i<=n;i++)
{
lca[0][i]=fget(1,1,2*n,l[i],r[i]).second;
}
for(int i=1;i<20;i++)
{
for(int j=1;j<=n;j++)
{
lca[i][j]=lca[i-1][lca[i-1][j]];
}
}
for(int i=1;i<=k;i++)
{
int a,b;
cin>>a>>b;
fun(a,b);
}
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |