Submission #529898

#TimeUsernameProblemLanguageResultExecution timeMemory
529898fhvirusRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
334 ms40288 KiB
#include <bits/stdc++.h> using namespace std; struct MinMax { int mn, mx; MinMax (int _mn = INT_MAX, int _mx = INT_MIN): mn(_mn), mx(_mx) {} const MinMax operator + (const MinMax& o) const { return MinMax(min(mn, o.mn), max(mx, o.mx)); } }; struct SGT { int n; vector<MinMax> val; SGT (const vector<MinMax>& v): n(v.size()), val(n * 2) { for (int i = 0; i < n; ++i) val[i + n] = v[i]; for (int i = n - 1; i > 0; --i) val[i] = val[i << 1] + val[i << 1 | 1]; } MinMax query(int l, int r) const { MinMax res; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = res + val[l++]; if (r & 1) res = res + val[--r]; } return res; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, K, M; cin >> N >> K >> M; vector<vector<int>> ono(N + 2); for (int A, B, lb, rb, i = 1; i <= M; ++i) { cin >> A >> B; if (A < B) lb = A, rb = min(A + K, B); else rb = A + 1, lb = max(B + 1, A - K + 1); ono[lb].emplace_back( B); ono[rb].emplace_back(-B); } vector<MinMax> go(1); go.reserve(N + 1); multiset<int> ms; for (int i = 1; i <= N; ++i) { for (const int& v: ono[i]) { if (v > 0) ms.insert(v); else ms.erase(ms.find(-v)); } int mn = i, mx = i; if (!ms.empty()) { mn = min(mn, *begin(ms)); mx = max(mx, *rbegin(ms)); } go.emplace_back(mn, mx); } int lg = __lg(N) + 1; vector<SGT> jmp(1, go); for (int l = 1; l <= lg; ++l) { for (int i = 1; i <= N; ++i) { MinMax tmp = jmp[l - 1].query(i, i); go[i] = jmp[l - 1].query(tmp.mn, tmp.mx); } jmp.emplace_back(go); } int Q; cin >> Q; for (int S, T, i = 1; i <= Q; ++i) { cin >> S >> T; MinMax range = jmp[lg].query(S, S); if (range.mn > T or T > range.mx) { cout << -1 << '\n'; continue; } range = MinMax(S, S); int ans = 0; for (int l = lg; l >= 0; --l) { MinMax tmp = jmp[l].query(range.mn, range.mx); if (tmp.mn > T or T > tmp.mx) { ans += (1 << l); range = tmp; } } cout << ans + 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...