Submission #1194579

#TimeUsernameProblemLanguageResultExecution timeMemory
1194579biankRailway Trip 2 (JOI22_ho_t4)C++20
27 / 100
2108 ms460256 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; const int SZ = 1 << 17; const int INF = 1e9; int maxi[2 * SZ], mini[2 * SZ]; template<typename T> void chmin(T &x, T v) { if (x > v) x = v; } template<typename T> void chmax(T &x, T v) { if (x < v) x = v; } void update(int l, int r, int v) { //cerr << l << ' ' << r << ' ' << v << '\n'; for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) { if (l & 1) { chmax(maxi[l], v); chmin(mini[l], v); l++; } if (r & 1) { --r; chmax(maxi[r], v); chmin(mini[r], v); } } } int queryMax(int i) { int res = maxi[i += SZ]; while (i /= 2) chmax(res, maxi[i]); return res; } int queryMin(int i) { int res = mini[i += SZ]; while (i /= 2) chmin(res, mini[i]); return res; } int askMin(int l, int r) { int res = INF; for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) { if (l & 1) chmin(res, mini[l++]); if (r & 1) chmin(res, mini[--r]); } return res; } int askMax(int l, int r) { int res = -INF; for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) { if (l & 1) chmax(res, maxi[l++]); if (r & 1) chmax(res, maxi[--r]); } return res; } map<pair<ii, int>, ii> memo; ii up(ii p, int k) { pair<ii, int> u = {p, k}; if (memo.count(u)) return memo[u]; if (k == 0) { auto [l, r] = p; int newL = askMin(l, r + 1); int newR = askMax(l, r + 1); ii newP = {newL, newR}; return memo[u] = newP; } return memo[u] = up(up(p, k - 1), k - 1); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, m; cin >> n >> k >> m; forn(i, 2 * SZ) mini[i] = INF, maxi[i] = -INF; forn(i, n) update(i, i + 1, i); forn(i, m) { int a, b; cin >> a >> b; --a, --b; if (a < b) { update(a, min(a + k, b), b); } else { update(max(a - k + 1, b + 1), a + 1, b); } } vi left(n), right(n); forn(i, n) left[i] = queryMin(i); forn(i, n) right[i] = queryMax(i); forn(i, 2 * SZ) mini[i] = INF, maxi[i] = -INF; forn(i, n) mini[i + SZ] = left[i], maxi[i + SZ] = right[i]; dforsn(i, 1, SZ) { mini[i] = min(mini[2 * i], mini[2 * i + 1]); maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]); } int q; cin >> q; forn(_, q) { int s, t; cin >> s >> t; --s, --t; int dist = 1; ii p = {s, s}; dforn(k, 20) { ii newP = up(p, k); if (!(newP.fst <= t && t <= newP.snd)) { p = newP; dist += 1 << k; } } p = up(p, 0); if (p.fst <= t && t <= p.snd) cout << dist << '\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...