제출 #721911

#제출 시각아이디문제언어결과실행 시간메모리
721911drdilyorEvent Hopping (BOI22_events)C++17
60 / 100
804 ms99952 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9 + 1e5; struct event { int l, r, i; }; struct segtree { int n; vector<pair<int,int>> t; segtree(int n) : n(n), t(n*4, {-1, -1}) {} void update(int i, const pair<int,int>& x) { t[i+=n] = x; for (i /= 2; i >= 1; i/= 2) { t[i] = max(t[i*2], t[i*2+1]); } } pair<int,int> query(int l, int r) { l += n; r += n; pair<int,int> res{-1,-1}; while (l <= r) { if (l%2==1) res = max(res, t[l++]); if (r%2==0) res = max(res, t[r--]); l /= 2; r /= 2; } return res; } }; int subtask_5(int n, int m, int k, vector<event>& ev, vector<event>& og) { segtree mxr(k); for (int i = 0; i < n;i ++) { mxr.update(ev[i].l, {ev[i].r, i}); } vector jmp(20, vector(n, -1)); for (int i = 0; i < n; i++) { pair<int,int> mx = mxr.query(0, ev[i].r); if (mx.first != ev[i].r) jmp[0][i] = mx.second; } for (int j = 1; j < 20; j++) for (int i = 0; i < n;i++) if (jmp[j-1][i] != -1) jmp[j][i] = jmp[j-1][jmp[j-1][i]]; vector<int> iof(n); for (int i = 0; i < n; i++) iof[ev[i].i] = i; while (m--) { int s, e; cin >> s >> e; s--;e--; if (s == e) { cout << "0\n"; continue; } if (og[e].l <= og[s].r && og[s].r <= og[e].r) { cout << "1\n"; continue; } if (og[e].r < og[s].r) { cout << "impossible\n"; continue; } int si = iof[s], ei = iof[e]; int res = 0; for (int j = 19; j >= 0; j--) { if (jmp[j][si] != -1 && ev[jmp[j][si]].r < ev[ei].l) { si = jmp[j][si]; res += 1<<j; } } int j = jmp[0][si]; if (j != -1 && jmp[0][j] != -1 && ev[ei].l <= ev[jmp[0][j]].r) { cout << res+2 << '\n'; } else { cout << "impossible\n"; } } return 0; } int subtask_4(int n, int m, int k, vector<event>& ev, vector<event>& og) { while (m--) { int s, e; cin >> s >> e; s--;e--; if (s == e) { cout << "0\n"; continue; } int si = 0, ei = 0; for (int j = 0; j < n; j++) { if (ev[j].i == s) si = j; if (ev[j].i == e) ei = j; } int res = 0; bool found = 0; int left = ev[ei].l; set<int> st; for (int j = n-1; j >= 0; j--) { auto [l,r,_i] = ev[j]; if (r > ev[ei].r) continue; if (r < left) { if (st.empty()) break; left = *st.begin(); if (r < left) break; st.clear(); res++; } if (j == si) { res++; found = 1; break; } st.insert(l); continue; } if (found) cout << res << '\n'; else cout << "impossible\n"; } return 0; } int subtask_3(int n, int m, int k, vector<event>& ev, vector<event>& og) { vector ans(n, vector(n, inf)); vector<int> mnl(k, inf); for (auto [l, r, i] :ev) { mnl[r] = min(mnl[r], l); } for (int ei = n-1; ei >= 0; ei--) { int res = 0; int lb = ev[ei].l, rb = ev[ei].r; for (int j = n-1; j >= 0; j--) { auto [l,r,_i] = ev[j]; if (r > ev[ei].r) continue; if (r < lb) { int mn = inf; for (int i = lb; i <= rb; i++) mn = min(mn, mnl[i]); lb = mn; if (r < lb) break; rb = r; res++; } ans[ei][j] = res + 1; } } while (m--) { int s, e; cin >> s >> e; s--;e--; if (s == e) { cout << "0\n"; continue; } int si = 0, ei = 0; for (int j = 0; j < n; j++) { if (ev[j].i == s) si = j; if (ev[j].i == e) ei = j; } if (ans[ei][si] < inf) cout << ans[ei][si] << '\n'; else cout << "impossible\n"; } return 0; } int subtask_1(int n, int m, int k, vector<event>& ev, vector<event>& og) { vector<int> next(n, -1), dist(n, inf), cc(n, -1); for (int i = 1; i < n; i++) { if (ev[i-1].l <= ev[i].r) next[i-1] = i; } cc[n-1] = 0; for (int i = n-2; i >= 0; i--) { if (next[i] !=-1) { dist[i] = min(dist[i], 1 + dist[next[i]]); cc[i] = cc[i+1]; } else cc[i] = cc[i+1]+1; } vector<int> iof(n); for (int i = 0; i < n; i++) iof[ev[i].i] = i; while (m--) { int s, e; cin >> s >> e; s--;e--; s = iof[s], e = iof[e]; if (cc[s] != cc[e] || dist[s] < dist[e]) cout << "impossible\n"; else cout << dist[s] - dist[e] << '\n'; } return 0; } int main() { int n, m; cin >> n >> m; vector<event> ev(n), og; map<int,int> comp; int _i = 0; for (auto& [s, e, i] : ev) { cin >> s >> e; comp[s] = comp[e] = 0; i = _i++; } int k = 0; for (auto& mp : comp) mp.second = k++; for (auto& [s, e, i] : ev) s = comp[s], e = comp[e]; og = ev; sort(ev.begin(), ev.end(), [&](auto& a, auto& b) { return a.r == b.r ? a.l < b.l : a.r < b.r ; }); bool overlap = 0; for (int i = 0; i+1 < n;i ++) { if (ev[i].l > ev[i+1].l) overlap = 1; } //for (auto[a,b,c] : ev) cout << a << ' ' << b << ' ' << c <<'\n'; if (!overlap) return subtask_5(n, m, k, ev, og); else if (n <= 5000) return subtask_3(n, m, k, ev, og); else if (m <= 100) return subtask_4(n, m, k, ev, og); else return subtask_1(n, m, k, ev, og); }
#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...