제출 #1187490

#제출 시각아이디문제언어결과실행 시간메모리
1187490qwushaEvent Hopping (BOI22_events)C++20
0 / 100
315 ms44944 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define int long long typedef long long ll; typedef long double ld; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); int inf = 1e15; int n; vector<int> dtl; vector<vector<int>> gl; vector<int> col; int curco = 0; void dfsl(int v, int p = -1, int d=0) { dtl[v] = d; for (auto u : gl[v]) { if (u != p) { dfsl(u, v, d + 1); } } } bool cmp(vector<int> a, vector<int> b) { if (a[1] == b[1]) { return a[0] < b[0]; } return (a[1] < b[1]); } vector<vector<int>> b; struct segtree{ int sz = 1; vector<pair<int, int>> tree; void init() { while (sz < n) { sz <<= 1; } tree.resize(sz * 2 - 1, {inf, inf}); build(0,0,sz); } void build(int v, int l, int r) { if (r - l == 1) { if (l < n) { tree[v] = {b[l][0], b[l][2]}; } return; } int m = (l + r) / 2; build(v * 2 + 1, l, m); build(v * 2 + 2, m, r); tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]); } pair<int, int> answer(int lq, int rq) { return ans(0,0,sz,lq,rq); } pair<int, int> ans(int v, int l, int r, int lq, int rq) { if (lq <= l && r <= rq) { return tree[v]; } if (lq >= r || rq <= l) { return {inf, inf}; } int m = (l + r) / 2; auto a1 = ans(v * 2 + 1, l, m, lq, rq), a2 = ans(v * 2 + 2, m, r, lq, rq); return min(a1, a2); } }; signed main() { int q; cin >> n >> q; gl.resize(n); dtl.resize(n); col.resize(n); vector<vector<int>> a(n, vector<int>(3)); for (int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; a[i][2] = i; } b = a; auto ini = a; sort(a.begin(), a.end()); sort(b.begin(), b.end(), cmp); vector<int> coolle; segtree tree; tree.init(); vector<int> par_to_lef(n); for (int i = 0; i < n; i++) { par_to_lef[i] = i; } for (int i = n - 1; i >= 0; i--) { int ind = b[i][2]; int beg = b[i][0]; int end = b[i][1]; int l = -1, r = n - 1; while (r - l > 1) { int mid = (l + r) / 2; if (b[mid][1] >= beg) { r = mid; } else { l = mid; } } auto re = tree.answer(r, ind + 1); if (re.fi < beg) { par_to_lef[ind] = re.se; gl[ind].push_back(re.se); gl[re.se].push_back(ind); } else { coolle.push_back(ind); } } curco = 0; for (auto el : coolle) { dfsl(el); } int logn = 3, vallog = 1; while (vallog < n) { vallog *= 2; logn++; } vector<vector<int>> upstl(logn, vector<int>(n)); for (int i = 0; i < n; i++) { upstl[0][i] = par_to_lef[i]; } for (int j = 1; j < logn; j++) { for (int i = 0; i < n; i++) { upstl[j][i] = upstl[j - 1][upstl[j - 1][i]]; } } for (int qw = 0; qw < q; qw++) { int s, e; cin >> s >> e; s--; e--; int curu = e; for (int i = logn - 1; i >= 0; i--) { if (ini[upstl[i][curu]][0] > ini[s][0]) curu = upstl[i][curu]; } if (ini[s][1] > ini[curu][1]) { cout << "impossible" << '\n'; } else if (s == e) { cout << 0 << '\n'; } else { curu = par_to_lef[curu]; if (curu == s) { cout << dtl[e] - dtl[curu] << '\n'; } else if (ini[curu][0] <= ini[s][0]) { cout << 1 + dtl[e] - dtl[curu] << '\n'; } else { cout << "impossible" << '\n'; } } } }
#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...