Submission #949702

#TimeUsernameProblemLanguageResultExecution timeMemory
949702sysiaEvent Hopping (BOI22_events)C++17
100 / 100
482 ms51236 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 20; const int mod = 998244353; struct Tree{ vector<T>tab; int size = 1; Tree(int n){ while (size < n) size*=2; tab.assign(2*size, {oo, oo}); } void update(int x, T v){ x += size; tab[x] = min(tab[x], v); while (x){ x/=2; tab[x] = min(tab[2*x], tab[2*x+1]); } } T query(int l, int r){ T ans = {oo, oo}; for (l += size-1, r += size+1; r-l>1; l/=2, r/=2) { if (!(l&1)) ans = min(ans, tab[l+1]); if (r&1) ans = min(ans, tab[r-1]); } return ans; } }; void solve(){ int n, q; cin >> n >> q; vector<T>a(n); vector<int>s; for (auto &[l, r]: a){ cin >> l >> r; s.emplace_back(l); s.emplace_back(r); } sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); auto get = [&](int x){ return (int)(lower_bound(s.begin(), s.end(), x)-s.begin());}; for (auto &[l, r]: a){ l = get(l); r = get(r); debug(l, r); } int m = (int)s.size(); vector<vector<int>>L(m), R(m); for (int i = 0; i<n; i++){ auto [l, r] = a[i]; L[l].emplace_back(i); R[r].emplace_back(i); } vector up(n+1, vector<int>(K)); Tree t(m+1); for (int i = 0; i<n; i++) t.update(a[i].second, {a[i].first, i}); //przedzial o minimalnym lewym koncu, z ktorego da sie doskoczyc na i-ty for (int rep = 0; rep < m; rep++){ for (auto i: L[rep]){ auto [left, prev] = t.query(a[i].first, a[i].second); up[i][0] = (prev == oo ? i : prev); debug(i, up[i][0]); } } for (int j = 1; j<K; j++){ for (int i = 0; i<n;i++){ up[i][j] = up[up[i][j-1]][j-1]; } } while (q--){ int l, r; cin >> l >> r; --l;--r; debug(l, r); int ans = 0; int ll = 0, rr = n; while (rr >= ll){ int mid = (ll+rr)/2; int curr = r; for (int i = K-1; i>=0; i--){ // debug(i, l, up[l][i]); if (mid&(1<<i)){ curr = up[curr][i]; } } //umiem doskoczyc do a[curr] //czy z l da sie przeskoczyc na curr kiedys(?) --> a[curr].second >= a[l].second >= a[curr].first; if (a[curr].first > a[l].second) { ll = mid+1; } else { ans = mid; rr = mid-1; } } for (int i = K-1; i>=0; i--){ if (ans&(1<<i)){ r = up[r][i]; } } debug(l, r); //czy z l da sie przeskoczyc na r if (a[r].first <= a[l].second && a[l].second <= a[r].second){ cout << ans + (l!=r) << "\n"; } else { cout << "impossible\n"; } } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) 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...