Submission #898044

#TimeUsernameProblemLanguageResultExecution timeMemory
898044GrindMachineEvent Hopping (BOI22_events)C++17
100 / 100
111 ms22612 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "impossible" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* read the edi a long time ago, dont remember much from there except binary lifting */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; const int LOG = 17; template<typename T> struct segtree { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { pii a; }; data neutral = {{inf1,inf1}}; data merge(data &left, data &right) { data curr; curr.a = min(left.a,right.a); return curr; } void create(int i, T v) { } void modify(int i, T v) { tr[i].a = v; } /*=======================================================*/ int n; vector<data> tr; segtree() { } segtree(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } data query(int l, int r) { data resl = neutral, resr = neutral; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, tr[l++]); if (!(r & 1)) resr = merge(tr[r--], resr); } return merge(resl, resr); } }; void solve(int test_case) { int n,q; cin >> n >> q; vector<pii> a(n+5); rep1(i,n) cin >> a[i].ff >> a[i].ss; auto cmp = [&](array<int,3> ar1, array<int,3> ar2){ if(ar1[1] != ar2[1]) return ar1[1] < ar2[1]; return ar1[0] < ar2[0]; }; vector<array<int,3>> b(n+5); rep1(i,n) b[i] = {a[i].ff,a[i].ss,i}; sort(b.begin()+1,b.begin()+n+1,cmp); rep1(i,n) a[i] = {b[i][0],b[i][1]}; vector<int> sorted_ind(n+5); rep1(i,n) sorted_ind[b[i][2]] = i; int up[n+5][LOG], down[n+5][LOG]; vector<pii> enter(n+5); rep1(i,n){ auto [l,r] = a[i]; int lo = 1, hi = n; int first = -1; while(lo <= hi){ int mid = (lo+hi) >> 1; if(l <= a[mid].ss){ first = mid; hi = mid-1; } else{ lo = mid+1; } } assert(first != -1); pii px = {r,i}; amax(enter[first],px); } pii best = {-1,-1}; int ptr = 1; rep1(i,n){ amax(best,enter[i]); up[i][0] = best.ss; } segtree<pii> st(n+5); rep1(i,n) st.pupd(i,{a[i].ff,i}); rep1(i,n){ auto [l,r] = a[i]; int first = -1, last = -1; int lo = 1, hi = n; while(lo <= hi){ int mid = (lo+hi) >> 1; if(a[mid].ss >= l){ first = mid; hi = mid-1; } else{ lo = mid+1; } } lo = 1, hi = n; while(lo <= hi){ int mid = (lo+hi) >> 1; if(a[mid].ss <= r){ last = mid; lo = mid+1; } else{ hi = mid-1; } } assert(first != -1 and last != -1); pii best = st.query(first,last).a; down[i][0] = best.ss; } /* rep1(i,n){ auto [l,r] = a[i]; pii best = {r,i}; rep1(j,n){ if(j == i) conts; auto [lx,rx] = a[j]; if(lx <= r and rx >= r){ pii px = {rx,j}; amax(best,px); } } up[i][0] = best.ss; } rep1(i,n){ auto [l,r] = a[i]; pii best = {l,i}; rep1(j,n){ if(j == i) conts; auto [lx,rx] = a[j]; if(l <= rx and r >= rx){ pii px = {lx,j}; amin(best,px); } } down[i][0] = best.ss; } */ rep1(j,LOG-1){ rep1(i,n){ up[i][j] = up[up[i][j-1]][j-1]; down[i][j] = down[down[i][j-1]][j-1]; } } while(q--){ int i,j; cin >> i >> j; i = sorted_ind[i]; j = sorted_ind[j]; if(i == j){ cout << 0 << endl; conts; } if(a[i].ss > a[j].ss){ no; conts; } int ans = 0; rev(b,LOG-1,0){ int p = up[i][b]; if(a[p].ss < a[j].ss){ ans += (1<<b); i = p; } } rev(b,LOG-1,0){ int p = down[j][b]; if(a[p].ff > a[i].ff){ ans += (1<<b); j = p; } } int add = inf1; if(a[j].ff <= a[i].ss){ add = 1; } else{ j = down[j][0]; if(a[i].ss >= a[j].ff and a[i].ss <= a[j].ss){ add = 2; } } ans += add; if(ans > inf1) no; else cout << ans << endl; } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

Compilation message (stderr)

events.cpp: In function 'void solve(int)':
events.cpp:173:9: warning: unused variable 'ptr' [-Wunused-variable]
  173 |     int ptr = 1;
      |         ^~~
#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...