Submission #1120044

#TimeUsernameProblemLanguageResultExecution timeMemory
1120044ksujay2Escape Route 2 (JOI24_escape2)C++17
23 / 100
830 ms59416 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int BSZ = 300; const ll INF = 1e18; void upd(ll& x, ll y) { x = min(x, y); } int main() { int N, T; cin >> N >> T; vector<vector<int>> A(N), B(N); vector<int> M(N); for(int i = 0; i < N - 1; i++) { int Mi; cin >> Mi; vector<int> imp; map<int, vector<int>> mp; for(int j = 0; j < Mi; j++) { int A, B; cin >> A >> B; mp[A].push_back(B); imp.push_back(A); } sort(imp.begin(), imp.end()); imp.resize(unique(imp.begin(), imp.end())-imp.begin()); reverse(imp.begin(), imp.end()); int E = T; for(int j : imp) { bool nw = false; for(int e : mp[j]) { if(E > e) E = e, nw = true; } if(nw) { A[i].push_back(j); B[i].push_back(E); M[i]++; } } reverse(A[i].begin(), A[i].end()); reverse(B[i].begin(), B[i].end()); A[i].push_back(A[i][0] + T); B[i].push_back(B[i][0] + T); } int Q; cin >> Q; vector<vector<pair<int, int>>> queries(N); for(int i = 0; i < Q; i++) { int L, R; cin >> L >> R; queries[L-1].push_back({R-1, i}); } vector<vector<int>> nxt(N); vector<vector<vector<int>>> prv(N); for(int i = 0; i < N; i++) { nxt[i].resize(M[i]); prv[i].resize(M[i]); } for(int i = 0; i < N - 2; i++) { int k = 0; for(int j = 0; j < M[i]; j++) { while(B[i][j] > A[i+1][k]) k++; nxt[i][j] = k; prv[i + 1][k % M[i+1]].push_back(j); } } vector<ll> ans(Q, INF); vector<vector<ll>> D(N); for(int i = 0; i < N; i++) { if(M[i] > BSZ) { D[i].assign(M[i], INF); for(int j = 0; j < M[i]; j++) D[i][j] = 0; for(int j = i; j < N - 2; j++) { D[j + 1].assign(M[j + 1], INF); for(int k = 0; k < M[j]; k++) { upd(D[j + 1][nxt[j][k] % M[j + 1]], D[j][k] + A[j + 1][nxt[j][k]] - A[j][k]); } } vector<ll> rans(N, INF); for(int j = i; j < N - 1; j++) { for(int k = 0; k < M[j]; k++) { upd(rans[j + 1], D[j][k] + B[j][k] - A[j][k]); } } for(auto [u, v] : queries[i]) { ans[v] = rans[u]; } } } vector<int> h(N); vector<ll> d(N); function<void(int, int)> dfs = [&] (int i, int j) { if(M[i] <= BSZ) { for(auto [u, v] : queries[i]) { upd(ans[v], B[u-1][h[u-1]] - A[u-1][h[u-1]] + d[i] - d[u-1]); } } for(int u : prv[i][j]) { h[i-1] = u; d[i-1] = d[i] + A[i][nxt[i-1][u]] - A[i-1][u]; dfs(i-1, u); } }; for(int i = 0; i < M[N-2]; i++) { dfs(N - 2, i); } for(ll a : ans) cout << a << endl; }
#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...