Submission #1098174

#TimeUsernameProblemLanguageResultExecution timeMemory
1098174rifat414141Event Hopping (BOI22_events)C++17
30 / 100
105 ms30792 KiB
#include <bits/stdc++.h> #define int long long int #define endl '\n' using namespace std; const int N = 1e5 + 10; const int INF = 1e18; const int LOGN = 20; int arr[N]; // pair<int, int> segment_tree[4 * N]; int up[N][LOGN]; int par[N]; // void build(int id, int l, int r) // { // if (l == r) // { // segment_tree[id] = {arr[l - 1], l - 1}; // return; // } // int mid = (l + r) / 2; // build(2 * id, l, mid); // build(2 * id + 1, mid + 1, r); // segment_tree[id] = min(segment_tree[2 * id], segment_tree[2 * id + 1]); // return; // } // pair<int, int> range(int id, int l, int r, int L, int R) // { // if (R < l || L > r) // { // return {INF, INF}; // } // if (L <= l && r <= R) // { // return segment_tree[id]; // } // int mid = (l + r) / 2; // pair<int, int> x = range(2 * id, l, mid, L, R); // pair<int, int> y = range(2 * id + 1, mid + 1, r, L, R); // return min(x, y); // } struct Seg { int siz; vector<pair<int, int>> v; void init(int n) { siz = 1; while (siz < n) siz *= 2; v.assign(siz * 2, make_pair(INF, -1)); } pair<int, int> merge(pair<int, int> x, pair<int, int> y) { pair<int, int> res; res.first = min(x.first, y.first); if (x.first == y.first) res.second = min(x.second, y.second); else if (res.first == x.first) res.second = x.second; else res.second = y.second; return res; } void set(int i, pair<int, int> p, int x, int lx, int rx) { if (rx - lx == 1) { v[x] = merge(p, v[x]); return; } int m = (lx + rx) / 2; if (i < m) set(i, p, 2 * x + 1, lx, m); else set(i, p, 2 * x + 2, m, rx); v[x] = merge(v[2 * x + 1], v[2 * x + 2]); } void set(int i, pair<int, int> p) { set(i, p, 0, 0, siz); } pair<int, int> range_mx(int l, int r, int x, int lx, int rx) { if (l >= rx || lx >= r) return make_pair(INF, -1); if (lx >= l && rx <= r) return v[x]; int m = (lx + rx) / 2; return merge(range_mx(l, r, 2 * x + 1, lx, m), range_mx(l, r, 2 * x + 2, m, rx)); } pair<int, int> range_mx(int l, int r) { return range_mx(l, r, 0, 0, siz); } }; void solve() { int n, q; cin >> n >> q; vector<pair<int, int>> v1; vector<pair<int, pair<int, int>>> v2; for (int i = 0; i < n; ++i) { int l, r; cin >> l >> r; v1.push_back({l, r}); v2.push_back({r, {l, i}}); } int brr[n]; sort(v2.begin(), v2.end()); for (int i = 0; i < n; ++i) { arr[i] = v2[i].second.first; brr[v2[i].second.second] = i; } // build(1, 1, n); Seg st; st.init(n + 1); for (int i = n - 1; i >= 0; i--) { st.set(i, make_pair(v2[i].second.first, i)); } for (int i = 0; i < n; ++i) { pair<int, pair<int, int>> p = {v2[i].second.first, {-1, -1}}; int it = lower_bound(v2.begin(), v2.end(), p) - v2.begin(); // cout << v2[i].first << ' ' << it << endl; if (it == i) { up[i][0] = par[i] = i; } else { // auto idx = range(1, 1, n, it + 1, i + 1); up[i][0] = par[i] = (st.range_mx(it, i)).second; } } for (int i = 1; i < LOGN; ++i) { for (int j = 0; j < n; ++j) { up[j][i] = up[up[j][i - 1]][i - 1]; } } while (q--) { int s, e; cin >> s >> e; if (s == e) { cout << 0 << endl; continue; } s--, e--; s = brr[s], e = brr[e]; int sl = v2[s].second.first, sr = v2[s].first; int el = v2[e].second.first, er = v2[e].first; if (s > e) { if (sl >= el && sr <= er) { cout << 1 << endl; continue; } else { cout << "impossible" << endl; continue; } } int curr = e; int ans = 0; for (int i = LOGN - 1; i >= 0; --i) { if (v2[up[curr][i]].first > sr) { ans += (1 << i); curr = up[curr][i]; } } if (v2[up[curr][0]].first > sr) { ans++; curr = up[curr][0]; } ans++; curr = up[curr][0]; if (v2[curr].first > sr) { cout << "impossible" << endl; continue; } else { cout << ans << endl; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("prime_subtractorization_input.txt", "r", stdin); // freopen("out.txt", "w", stdout); int t = 1; // cin >> t; for (int tt = 1; tt <= t; ++tt) { // cout << "Case #" << tt << ": "; solve(); } return 0; }
#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...