제출 #569159

#제출 시각아이디문제언어결과실행 시간메모리
569159sidonRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
566 ms39184 KiB
#include <bits/stdc++.h> using namespace std; const int Z = 1e5, B = 17; int N, K, M; struct ST { int a[2*Z] {}, minQry = 0; void update(int i, int v) { i += N; a[i] = max(a[i], minQry ? Z-v : v); } void build() { for(int i = N; --i; ) a[i] = max(a[2*i], a[2*i+1]); } int query(int l, int r) { int x {}; for(l += N, r += N + 1; l < r; l /= 2, r /= 2) { if(l & 1) x = max(x, a[l++]); if(r & 1) x = max(x, a[--r]); } return minQry ? Z-x : x; } int operator[](int i) { return minQry ? Z - a[i + N] : a[i + N]; } } s[2][B]; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> N >> K >> M; priority_queue<array<int, 2>> q[2]; vector<array<int, 2>> g[2][N]; while(M--) { int l, r; cin >> l >> r; --l, --r; if(l < r) g[1][l].push_back({r, min(l + K - 1, r)}); else g[0][max(l - K + 1, r)].push_back({-r, l}); } for(int i = 0; i < B; ++i) s[0][i].minQry = 1; for(int i = 0; i < N; ++i) { for(int j : {0, 1}) { for(auto k : g[j][i]) q[j].push(k); while(!empty(q[j]) && q[j].top()[1] < i) q[j].pop(); s[j][0].update(i, empty(q[j]) ? i : (j ? 1 : -1) * q[j].top()[0]); } } for(int j : {0, 1}) s[j][0].build(); for(int k = 0; k + 1 < B; ++k) { for(int j : {0, 1}) { for(int i = 0; i < N; ++i) s[j][k + 1].update(i, s[j][k].query(s[0][k][i], s[1][k][i])); s[j][k + 1].build(); } } cin >> M; while(M--) { int l, t; cin >> l >> t; --l, --t; int r = l, x {}; for(int i = B; i--; ) { int sl = s[0][i].query(l, r); int sr = s[1][i].query(l, r); if(sl > t || t > sr) { l = sl, r = sr; x |= 1<<i; } } cout << (++x > N ? -1 : x) << '\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...