#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <numeric> #include <deque> #include <random> #include <unordered_map> #include <unordered_set> #include <queue> #include <stack> #include <string> #include <iomanip> #include <fstream> #include <bitset> #include <ctime> #include <cstdio> #include <chrono> #include <functional> #include <x86intrin.h> #include <cassert> #include <list> #include <iterator> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #ifdef LOCAL bool local = true; #else bool local = false; #endif /*<-------DEFINES START------->*/ #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define for1(n) for (int i = 1; i < n; ++i) #define for0(n) for (int i = 0; i < n; ++i) #define rep(i, j, n) for (int i = (j); i < (n); ++i) #define rrep(i, j, n) for (int i = (j); i >= (n); --i) #define debug(fmt, ...) \ fprintf(stderr, "[%d] " fmt "\n", LINE, ##__VA_ARGS__) #define lb lower_bound #define ub upper_bound #define rsun(a) a.resize(unique(a.begin(), a.end())-a.begin()) #define re return #define con continue #define pb push_back #define pob pop_back; #define sz(x) (int)size(x) #define fi first #define se second using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector<int>; using vll = vector<long long>; using pii = pair<int, int>; using pll = pair<long long, long long>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>; using vvll = vector<vector<long long>>; using vpii = vector<pair<long long, long long>>; using vvpii = vector<vpii>; using tiii = tuple<int, int, int>; /*<-------DEFINES END------->*/ /*<-------TEMPLATES START------->*/ template<typename T> istream& operator>>(istream& in, vector<T>& a) { for (T& i : a) in >> i; return in; } template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& a) { in >> a.fi >> a.se; return in; } template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& a) { out << a.fi << " " << a.se; return out; } template<typename T1, typename T2> istream& operator>>(istream& in, vector<pair<T1, T2>>& a) { for (pair<T1, T2>& i : a) in >> i.fi >> i.se; return in; } template<typename T> ostream& operator<<(ostream& out, const vector<T>& a) { for (auto i : a) { out << i << " "; } return out; } template<typename T1, typename T2> ostream& operator<<(ostream& out, vector<pair<T1, T2>>& a) { for (pair<T1, T2> i : a) out << i.fi << " " << i.se << endl; return out; } template<typename T1> ostream& operator<<(ostream& out, vector<vector<T1>>& a) { for (vector<T1> i : a) { for (T1 j : i) out << j << " "; out << endl; } return out; } template<typename T1, typename T2> inline T1 min(T1 a, T2 b) { b = (T1)b; return a > b ? b : a; } template<typename T1, typename T2> inline T1 max(T1 a, T2 b) { b = (T1)b; return a > b ? a : b; } template<typename T1, typename T2> inline void amin(T1& a, T2 b) { a = min(a, b); } template<typename T1, typename T2> inline void amax(T1& a, T2 b) { a = max(a, b); } /*<-------TEMPLATES END------->*/ double getTime() { return clock() / (double)CLOCKS_PER_SEC; } int randint(int start, int end) { return rand() % (end - start + 1) + start; } ll gcd(ll a, ll b) { if (a == 0) { return b; } return gcd(b % a, a); } ll gcd(ll a, ll b, ll& x, ll& y) { if (a == 0) { x = 0; y = 1; return b; } ll x1, y1, g = gcd(b % a, a, x1, y1); // (b % a) * x1 + a * y1 = g // a * x + b * y = g x = y1 - (b / a * x1); y = x1; return g; } ll bin_pow(ll a, ll b, ll MOD) { if (b == 0) { return 1 % MOD; } if (b % 2 == 0) { ll p = bin_pow(a, b / 2, MOD) % MOD; return p * p % MOD; } return a * bin_pow(a, b - 1, MOD) % MOD; } string run_num; void solve(int t); signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (local) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } // cin >> run_num; int tt = 1; // cin >> tt; rep(i, 1, tt + 1) { if (local) { cout << "Case #" << i << ":\n"; } solve(i); } if (local) { cout << "\n"; cout << fixed << "Time = " << getTime() << " ms\n"; } return 0; } /*<-------ACTUAL CODE STARTS HERE------->*/ #pragma GCC optimize("unroll-loops,Ofast") const int INF = 2e18, MOD = 1e9 + 7; const int N = 1e4 + 1000; struct ST { vpii t; void init(int n) { t.assign(4 * (n + 100), {INF, INF}); } void build(int v, int tl, int tr, vi& a) { if (tl + 1 == tr) { t[v] = {a[tl], tl}; re; } int tm = (tl + tr) / 2; build(2 * v + 1, tl, tm, a); build(2 * v + 2, tm, tr, a); t[v] = min(t[2 * v + 1], t[2 * v + 2]); } pii get(int v, int tl, int tr, int l, int r) { if (r <= tl || tr <= l) re {INF, INF}; if (l <= tl && tr <= r) re t[v]; int tm = (tl + tr) / 2; pii left = get(2 * v + 1, tl, tm, l, r), right = get(2 * v + 2, tm, tr, l, r); re min(left, right); } }; vpii vec; vvi gr; vvi bin_ups; void dfs(int u, int p) { bin_ups[0][u] = p; rep(i, 1, 20) { bin_ups[i][u] = bin_ups[i - 1][bin_ups[i - 1][u]]; } for (int v : gr[u]) { if (v != p) { dfs(v, u); } } } pii la(int u, int left, int right) { int cnt = 0; rrep(i, 19, 0) { auto [l1, r1] = vec[bin_ups[i][u]]; if (l1 > right) { cnt += 1ll << i; u = bin_ups[i][u]; } } re {u, cnt}; } void solve(int test) { int n, q; cin >> n >> q; vec.resize(n); cin >> vec; map<pii, int> mp; map<int, int> mp2; vi cords; for (auto [l, r] : vec) cords.pb(l), cords.pb(r); sort(all(cords)); rsun(cords); for (auto& [l, r] : vec) { int x = lb(all(cords), l) - cords.begin(); int y = lb(all(cords), r) - cords.begin(); mp2[x] = l; mp2[y] = r; l = lb(all(cords), l) - cords.begin(); r = lb(all(cords), r) - cords.begin(); } rep(i, 0, n) { mp[vec[i]] = i; } vi right(2 * n + 10, INF); for (auto [l, r] : vec) { amin(right[r], l); } ST t; t.init(2 * n + 10); t.build(0, 0, 2 * n + 10, right); gr.resize(n); vi roots; rep(i, 0, n) { auto [l, r] = vec[i]; auto [l1, r1] = t.get(0, 0, 2 * n + 10, l, r + 1); if (l1 != l) { // cout << i << " " << mp[{l1, r1}] << "!!!!\n"; gr[i].pb(mp[{l1, r1}]); gr[mp[{l1, r1}]].pb(i); } else { roots.pb(i); } } bin_ups.assign(20, vi(n + 1)); for (int u : roots) { dfs(u, u); } rep(i, 0, q) { int u, v; cin >> u >> v; u--, v--; if (u == v) { cout << 0 << "\n"; con; } auto [l, r] = vec[u]; auto [l3, r3] = vec[v]; if (r > r3) { cout << "impossible\n"; con; } auto [vrtx, cnt] = la(v, l, r); auto [l1, r1] = vec[vrtx]; if (l1 <= r && r <= r1) { cout << cnt + 1 << "\n"; con; } auto [l2, r2] = vec[bin_ups[0][vrtx]]; // cout << mp2[l1] << " " << mp2[r1] << " " << mp2[l2] << " " << mp2[r2] << "!!!!!\n"; if (r >= l2) { cout << cnt + 2 << "\n"; } else { cout << "impossible\n"; } } }

events.cpp: In function 'int main()':
events.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:193:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~