Submission #1194572

#TimeUsernameProblemLanguageResultExecution timeMemory
1194572biankRailway Trip 2 (JOI22_ho_t4)C++20
27 / 100
2095 ms3396 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; } /*struct Node { int value, index; bool active = false; }; Node operator+(Node lhs, Node rhs) { if (!lhs.active) return rhs; if (!rhs.active) return lhs; if (lhs.value < rhs.value) return lhs; return rhs; } Node st[2 * SZ]; int lazy[2 * SZ]; void pass(int u) { if (lazy[u] == INF) return; if (u < SZ) { lazy[2 * u] = min(lazy[2 * u], lazy[u]); lazy[2 * u + 1] = min(lazy[2 * u + 1], lazy[u]); } st[u].value = min(st[u].value, lazy[u]); lazy[u] = INF; } void updateRange(int s, int e, int v, int l = 0, int r = SZ, int u = 1) { pass(u); if (e <= l || r <= s) { return; } if (s <= l && r <= e) { lazy[u] = v; return pass(u); } int m = (l + r) / 2; updateRange(s, e, v, l, m, 2 * u); updateRange(s, e, v, m, r, 2 * u + 1); st[u] = st[2 * u] + st[2 * u + 1]; } void deactivate(int p, int l = 0, int r = SZ, int u = 1) { pass(u); if (u >= SZ) { st[u].active = false; return; } int m = (l + r) / 2; if (p < m) deactivate(p, l, m, 2 * u); else deactivate(p, m, r, 2 * u + 1); pass(2 * u), pass(2 * u + 1); st[u] = st[2 * u] + st[2 * u + 1]; }*/ 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; } 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]); } //forn(i, n) cerr << left[i] << ' ' << right[i] << '\n'; int q; cin >> q; forn(_, q) { int s, t; cin >> s >> t; --s, --t; int dist = 1; int l = left[s], r = right[s]; bool flag = true; while (l > t || r < t) { //cerr << l << ' ' << r << '\n'; int newL = askMin(l, r + 1); int newR = askMax(l, r + 1); if (l == newL && r == newR) { flag = false; break; } dist++, l = newL, r = newR; } if (flag) 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...