제출 #1098248

#제출 시각아이디문제언어결과실행 시간메모리
1098248rifat414141Event Hopping (BOI22_events)C++17
100 / 100
104 ms31556 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], crr[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; crr[i] = v2[i].second.second; } 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] = idx.second; } } for (int j = 1; j < LOGN; ++j) { for (int i = 0; i < n; ++i) { if (j == 1) up[i][j] = up[par[i]][j - 1]; else up[i][j] = up[up[i][j - 1]][j - 1]; // 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--; int ogs = brr[s], oge = brr[e]; int sl = v2[ogs].second.first, sr = v2[ogs].first; int el = v2[oge].second.first, er = v2[oge].first; if (ogs > oge) { if (sr >= el && sr <= er) { cout << 1 << endl; continue; } else { cout << "impossible" << endl; continue; } } int curr = oge; int ans = 0; int mn = sr; for (int i = LOGN - 1; i >= 0; --i) { if (v2[up[curr][i]].second.first > mn) { ans += (1 << i); curr = up[curr][i]; } } if (v1[crr[curr]].first > mn) { ans++; curr = up[curr][0]; } // cout << curr << endl; ans++; // curr = up[curr][0]; if (v1[crr[curr]].first > mn) { 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; }

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'void solve()':
events.cpp:167:13: warning: unused variable 'sl' [-Wunused-variable]
  167 |         int sl = v2[ogs].second.first, sr = v2[ogs].first;
      |             ^~
#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...