#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const string ny[2] = {"No", "Yes"};
#define x first
#define y second
vector<vector<ll>> G(200000);
vector<vector<ll>> P(24,vector<ll>(200000,0));
vector<ll> v(200000,0);
vector<ll> v2(200000,0);
ll c;
void dfs(ll node, ll p,ll d)
{
if(v[node]!=0) return;
v2[node]=c;
v[node]=d;
P[0][node]=p;
for(int i=1; i<24; i++)
P[i][node]=P[i-1][P[i-1][node]];
for(auto i:G[node])
dfs(i,node,d+1);
}
ll Padre_A_Distancia_D(ll a, ll d)
{
for(int i=23; i>=0; i--)
if((d&(1<<i))!=0)
a=P[i][a];
return a;
}
ll lca(ll a, ll b)
{
ll cont=0;
if(v[a]<v[b]) return 1e9;
cont+=v[a]-v[b];
a=Padre_A_Distancia_D(a,v[a]-v[b]);
if(a==b) return cont;
else return 1e9;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll n,q;
cin>>n>>q;
v.resize(n+2);
vector<pair<ll,ll>> cad;
vector<pair<ll,ll>> input;input.push_back({0,0});
for(int i=1; i<=n; i++)
{
ll a,b;
cin>>a>>b;
input.push_back({a,b});
cad.push_back({a,i});
cad.push_back({b,i});
}
sort(cad.begin(),cad.end());
set<ll> s;
for(int i=0; i<cad.size(); i++)
{
vector<ll> temp,temp2;
ll a=i;
while(i<cad.size()&&cad[a].x==cad[i].x){
temp.push_back(cad[i].y);
i++;
}
i--;
for(auto j:temp)
{
if(s.find(j)!=s.end())
temp2.push_back(j);
else s.insert(j);
}
for(auto j:temp2) for(auto k:s) if(j!=k)G[j].push_back(k);
for(auto j:temp2) if(s.find(j)!=s.end()) s.erase(j);
}
vector<ll> asdf(n+2,0);
for(int i=1; i<=n; i++)
{
for(auto j:G[i])
{
asdf[j]++;
}
}
for(int i=1; i<=n; i++)
if(asdf[i]==0)
{
dfs(i,0,1);
c=i;
}
for(int i=0; i<q; i++)
{
ll a,b;
cin>>a>>b;
if(v[b]<v[a]||v2[a]!=v2[b])
cout<<"impossible";
else cout<<v[b]-v[a];
cout<<"\n";
}
return 0;
}
Compilation message
vault.cpp: In function 'int main()':
vault.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0; i<cad.size(); i++)
| ~^~~~~~~~~~~
vault.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while(i<cad.size()&&cad[a].x==cad[i].x){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
45884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
45884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
45888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
45888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
45888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
45884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
45888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
45884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
45888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
45884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
