//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "Ofast", "O3")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pi;
constexpr ll inf = 2e9, xn = 1e5 + 5, s = 317;
ll d[xn], p[xn], sx[xn], x[xn], m[s];
pi e[xn];
int main()
{
Fast
ll n, q;
cin >> n >> q;
rep(i, 0, n) cin >> e[i].Y.X >> e[i].X;
rep(i, 0, n) e[i] = {-e[i].X, {-e[i].Y.X, i}};
sort(e, e + n);
rep(i, 0, s) m[i] = -inf;
rep(i, 0, n)
{
sx[i] = x[i] = -1;
rep(j, 0, i / s + 1) if(e[i].X <= m[j])
{
rep(k, j * s, min((j + 1) * s, i)) if(e[i].X <= e[k].Y.X)
{
if(k / s < i / s) sx[i] = k, d[i] = 1;
else if(sx[k] >= 0) sx[i] = sx[k], d[i] = d[k] + 1;
x[i] = k;
break;
}
break;
}
m[i / s] = max(e[i].Y.X, m[i / s]), p[e[i].Y.Y] = i;
}
while(q--)
{
ll l, r, ans = 0;
cin >> l >> r;
if(l == r)
{
cout << "0\n";
continue;
}
l = p[l - 1], r = p[r - 1];
if(e[l].X < e[r].X)
{
cout << "impossible\n";
continue;
}
if(e[l].X == e[r].X)
{
cout << "1\n";
continue;
}
ll y = l;
while(sx[y] >= r) ans += d[y], y = sx[y];
while(x[y] >= r) y = x[y], ans++;
if(r == y)
{
cout << ans << '\n';
continue;
}
bool f = 0;
rep(i, r, y) if(e[y].X <= e[i].Y.X)
{
ans++, f = 1;
break;
}
if(f) cout << ans << '\n';
else cout << "impossible\n";
}
}
~
~
~
Compilation message
events.cpp:82:1: error: expected class-name before '~' token
82 | ~
| ^
