Submission #529484

#TimeUsernameProblemLanguageResultExecution timeMemory
529484fhvirusRailway Trip 2 (JOI22_ho_t4)C++17
0 / 100
499 ms25572 KiB
#include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef pair<int, int> pii; #define pb emplace_back #define AI(x) begin(x),end(x) #define ff first #define ss second #ifdef OWO #define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args) template<class I> void LKJ(I&&x) { cerr << x << endl; } template<class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); } template<class I> void OI(I a, I b) { while (a != b) cerr << *a << ' ', ++a; cerr << endl; } #else #define debug(...) 0 #define OI(...) 0 #endif struct RMQ { int n; vector<int> val; RMQ() = default; void build(int i, int l, int r, const vector<int>& v) { if (l == r) { val[i] = v[l]; return; } int m = (l + r) / 2; build(i * 2, l, m, v); build(i * 2 + 1, m + 1, r, v); val[i] = max(val[i * 2], val[i * 2 + 1]); } void build(const vector<int>& v) { n = v.size(); val.resize(n * 4); build(1, 1, n, v); } int query(int i, int l, int r, int ql, int qr) { if (ql <= l and r <= qr) return val[i]; int m = (l + r) / 2; int ans = 0; if (ql <= m) ans = max(ans, query(i * 2, l, m, ql, qr)); if (m < qr) ans = max(ans, query(i * 2 + 1, m + 1, r, ql, qr)); return ans; } int query(int l, int r) { return query(1, 1, n, l, r); } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, K; cin >> N >> K; int M; cin >> M; vector<int> A(M + 1), B(M + 1); for (int i = 1; i <= M; ++i) cin >> A[i] >> B[i]; int Q; cin >> Q; vector<int> S(Q + 1), T(Q + 1); for (int i = 1; i <= Q; ++i) cin >> S[i] >> T[i]; vector<vector<int>> ono(N + 1); for (int i = 1; i <= M; ++i) { assert(A[i] < B[i]); ono[A[i]].pb(B[i]); if (A[i] + K <= N) ono[A[i] + K].pb(-B[i]); } multiset<int> st; vector<int> rightmost(N + 1, 0); for (int i = 1; i <= N; ++i) { for (const int& v: ono[i]) { if (v > 0) st.insert(v); else { auto it = st.find(-v); st.erase(it); } } if (!st.empty()) rightmost[i] = max(i, *rbegin(st)); else rightmost[i] = i; } int lg = __lg(N) + 1; RMQ rmq; vector<vector<int>> jmp(lg + 1, vector<int>(N + 1, 0)); jmp[0] = rightmost; for (int l = 1; l <= lg; ++l) { rmq.build(jmp[l - 1]); for (int i = 1; i <= N; ++i) { int rb = jmp[l - 1][i]; jmp[l][i] = rmq.query(i, rb); } debug(l); OI(AI(jmp[l])); } for (int i = 1; i <= Q; ++i) { int s = S[i], t = T[i]; if (jmp[lg][s] < t) { cout << -1 << '\n'; continue; } int ans = 0; for (int l = lg; l >= 0; --l) if (jmp[l][s] < t) { ans += (1 << l); s = jmp[l][s]; } cout << ans + 1 << '\n'; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Main.cpp:96:3: note: in expansion of macro 'debug'
   96 |   debug(l);
      |   ^~~~~
Main.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define OI(...) 0
      |                 ^
Main.cpp:97:3: note: in expansion of macro 'OI'
   97 |   OI(AI(jmp[l]));
      |   ^~
#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...