Submission #866266

#TimeUsernameProblemLanguageResultExecution timeMemory
866266fanwenEvent Hopping (BOI22_events)C++17
100 / 100
128 ms17860 KiB
/** * author : pham van sam * created : 25 October 2023 (Wednesday) **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define clog if(false) cerr #endif template < class T, T (*f) (T, T), T (*e) ()> struct segment_tree { vector <T> it; int n; void update(int u, T p) { u += n - 1; it[u] = f(it[u], p); for(; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } void set(int u, T p) { u--; for (it[u += n] = p; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } T get(int p) { return it[p += n - 1]; } T get(int l, int r) { l--; T resl = e(), resr = e(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) resl = f(resl, it[l++]); if(r & 1) resr = f(it[--r], resr); } return f(resl, resr); } segment_tree(int n = 0) : n(n), it(n << 1 | 1) { fill(it.begin(), it.end(), T{}); } }; pair <int, int> op(pair <int, int> a, pair <int, int> b) { if(a.first == 0) return b; if(b.first == 0) return a; return a < b ? a : b; }; pair <int, int> e() { return make_pair(0, 0); }; const int MAXN = 1e5 + 5; const int LOG = 20; struct segment { int l, r, ind; friend ostream & operator << (ostream &out, const segment &a) { return out << "(" << a.l << ", " << a.r << ", " << a.ind << ")"; } } A[MAXN]; int n, q, anc[MAXN][LOG], pos[MAXN]; void you_make_it(void) { cin >> n >> q; vector <int> compress; for (int i = 1; i <= n; ++i) { cin >> A[i].l >> A[i].r; A[i].ind = i; compress.push_back(A[i].l); compress.push_back(A[i].r); } sort(compress.begin(), compress.end()); compress.erase(unique(compress.begin(), compress.end()), compress.end()); for (int i = 1; i <= n; ++i) { A[i].l = lower_bound(compress.begin(), compress.end(), A[i].l) - compress.begin() + 1; A[i].r = lower_bound(compress.begin(), compress.end(), A[i].r) - compress.begin() + 1; } sort(A + 1, A + n + 1, [&] (const segment &a, const segment &b) -> bool { return make_pair(a.l, a.r) < make_pair(b.l, b.r); }); // for (int i = 1; i <= n; ++i) clog << debug(A[i]) << '\n'; segment_tree <pair <int, int>, op, e> it((int) compress.size()); for (int i = 1; i <= n; ++i) { pos[A[i].ind] = i; it.update(A[i].r, make_pair(A[i].l, i)); auto [_, id] = it.get(A[i].l, A[i].r); anc[i][0] = id; // clog << anc[i][0] << " \n"[i == 1]; } for (int i = 1; i < LOG; ++i) { for (int u = 1; u <= n; ++u) { anc[u][i] = anc[anc[u][i - 1]][i - 1]; } } while(q--) { int u, v; cin >> u >> v; u = pos[u], v = pos[v]; if(u == v) { cout << "0\n"; continue; } if(A[u].r > A[v].r) { cout << "impossible\n"; continue; } if(A[u].r == A[v].r) { cout << "1\n"; continue; } int ans = 0; for (int i = LOG - 1; i >= 0; --i) { if(A[u].r < A[anc[v][i]].l) { ans += 1 << i; v = anc[v][i]; } } if(A[v].l <= A[u].r && A[u].r <= A[v].r) ans++; else { v = anc[v][0]; ans += 2; } if(A[v].l <= A[u].r && A[u].r <= A[v].r) cout << ans; else cout << "impossible"; cout << '\n'; // clog << u << " " << v << '\n'; } } signed main() { #ifdef LOCAL freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif auto start_time = chrono::steady_clock::now(); cin.tie(0), cout.tie(0) -> sync_with_stdio(0); you_make_it(); auto end_time = chrono::steady_clock::now(); cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); } // Dream it. Wish it. Do it.

Compilation message (stderr)

events.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = std::pair<int, int>; T (* f)(T, T) = op; T (* e)() = e]':
events.cpp:101:67:   required from here
events.cpp:19:9: warning: 'segment_tree<std::pair<int, int>, op, e>::n' will be initialized after [-Wreorder]
   19 |     int n;
      |         ^
events.cpp:18:16: warning:   'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > segment_tree<std::pair<int, int>, op, e>::it' [-Wreorder]
   18 |     vector <T> it;
      |                ^~
events.cpp:50:5: warning:   when initialized here [-Wreorder]
   50 |     segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |     ^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...