#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct SparseTable
{
int n;
vector<vector<T>> mat;
SparseTable(const vector<T>& a)
{
n = int(a.size());
int maxLog = 32 - __builtin_clz(n);
mat.resize(maxLog);
mat[0] = a;
for (int j = 1; j < maxLog; j++)
{
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++)
mat[j][i] = min(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
T get(int from, int to)
{
assert(0 <= from && from <= to && to <= n - 1);
int lg = 31 - __builtin_clz(to - from + 1);
return min(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
const int oo = 27081993;
const int LG = 17;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<pair<int, int>> a;
map<int, int> values;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
a.push_back({l, r});
values[l] = values[r] = 0;
}
int valueCnt = 0;
for (auto [k, _] : values)
values[k] = valueCnt++;
vector<pair<int, int>> minL(valueCnt, make_pair(oo, -1));
for (int i = 0; i < n; i++)
{
auto [l, r] = a[i];
l = values[l];
r = values[r];
a[i] = {l, r};
minL[r] = min(minL[r], make_pair(l, i));
}
SparseTable<pair<int, int>> st(minL);
vector<vector<int>> prev(n, vector<int>(LG, -1));
for (int i = 0; i < n; i++)
{
auto [l, id] = st.get(a[i].first, a[i].second);
if (l < a[i].first)
prev[i][0] = id;
}
for (int j = 0; j + 1 < LG; j++)
for (int i = 0; i < n; i++)
if (prev[i][j] >= 0)
prev[i][j + 1] = prev[prev[i][j]][j];
while (q--)
{
int s, t;
cin >> s >> t;
s--; t--;
if (s == t) cout << "0\n";
else if (a[t].first <= a[s].second && a[s].second <= a[t].second) cout << "1\n";
else if (a[s].second > a[t].second) cout << "impossible\n";
else
{
int ans = 1;
for (int i = LG - 1; i >= 0; i--)
if (prev[t][i] >= 0 && a[prev[t][i]].first > a[s].second)
{
ans += 1 << i;
t = prev[t][i];
}
if (prev[t][0] >= 0 && a[prev[t][0]].first <= a[s].second) ans++;
else ans = -1;
if (ans < 0) cout << "impossible\n"
else cout << ans << '\n';
}
}
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:99:42: error: expected ';' before 'else'
99 | if (ans < 0) cout << "impossible\n"
| ^
| ;
100 | else cout << ans << '\n';
| ~~~~
