제출 #1262587

#제출 시각아이디문제언어결과실행 시간메모리
1262587vlomaczkRailway Trip 2 (JOI22_ho_t4)C++20
100 / 100
521 ms39508 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int base = 1<<17; struct min_left { vector<int> t; void construct() { t.assign(2*base, INT_MAX); } void update(int a, int b, int val) { if(a==b) { t[a+base] = min(t[a+base], val); return; } a += base-1; b += base+1; while(a/2 != b/2) { if(a%2==0) t[a+1] = min(t[a+1], val); if(b%2==1) t[b-1] = min(t[b-1], val); a/=2; b/=2; } } int query(int x) { int ans = INT_MAX; x += base; while(x > 0) { ans = min(ans, t[x]); x/=2; } return ans; } }; struct max_right { vector<int> t; void construct() { t.assign(2*base, 0); } void update(int a, int b, int val) { if(a==b) { t[a+base] = max(t[a+base], val); return; } a += base-1; b += base+1; while(a/2 != b/2) { if(a%2==0) t[a+1] = max(t[a+1], val); if(b%2==1) t[b-1] = max(t[b-1], val); a/=2; b/=2; } } int query(int x) { int ans = 0; x += base; while(x > 0) { ans = max(ans, t[x]); x/=2; } return ans; } }; int maxlog = 16; struct segm_tree_max { vector<vector<int>> t; void build() { t.assign(maxlog+1, vector<int>(2*base, 0)); } void update(int x, int val, int i) { x += base; t[i][x] = val; x/=2; while(x>0) { t[i][x] = max(t[i][x+x], t[i][x+x+1]); x/=2; } } int query(int a, int b, int i) { if(a==b) return t[i][a+base]; a+=base-1; b+=base+1; int ans = INT_MIN; while(a/2!=b/2) { if(a%2==0) ans = max(ans, t[i][a+1]); if(b%2==1) ans = max(ans, t[i][b-1]); a/=2; b/=2; } return ans; } }; struct segm_tree_min { segm_tree_max stm; void build() { stm.build(); } void update(int x, int val, int i) { stm.update(x, -val, i); } int query(int a, int b, int i) { return -stm.query(a, b, i); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k; cin >> n >> k; min_left ml; ml.construct(); max_right mr; mr.construct(); for(int i=1; i<=n; ++i) { mr.update(i, i, i); ml.update(i, i, i); } int m; cin >> m; for(int i=0; i<m; ++i) { ll a, b; cin >> a >> b; if(a<b) { mr.update(a, min(a+k-1, b-1), b); } else { ml.update(max(a-k+1, b+1), a, b); } } vector<int> vml(n+1), vmr(n+1); for(int i=1; i<=n; ++i) { vml[i] = ml.query(i); vmr[i] = mr.query(i); } segm_tree_max stmax; stmax.build(); segm_tree_min stmin; stmin.build(); for(int i=1; i<=n; ++i) { stmax.update(i, vmr[i], 0); stmin.update(i, vml[i], 0); } for(int x=1; x<=maxlog; ++x) { for(int i=1; i<=n; ++i) { stmax.update(i, stmax.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x); stmin.update(i, stmin.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x); } } int q; cin >> q; while(q--) { int a, b; cin >> a >> b; ll ans = 0; pair<int, int> inv = {a, a}; for(int i=maxlog; i>=0; --i) { pair<int, int> new_inv = {stmin.query(inv.first, inv.second, i), stmax.query(inv.first, inv.second, i)}; if(new_inv.first <= b && b <= new_inv.second) continue; inv = new_inv; ans += 1LL<<i; } pair<int, int> new_inv = {stmin.query(inv.first, inv.second, 0), stmax.query(inv.first, inv.second, 0)}; if(new_inv.first <= b && b <= new_inv.second) cout << ans+1 << "\n"; else cout << "-1\n"; } 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...