Submission #1203022

#TimeUsernameProblemLanguageResultExecution timeMemory
1203022zeta7532Train (APIO24_train)C++20
0 / 100
50 ms19008 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL << 60); // ---- Persistent Segment Tree for point-add & range-sum ---- struct PST { struct Node { int l, r, sum; }; vector<Node> st; int N; PST(int _N): N(_N) { st.reserve(_N * 20); st.push_back({0,0,0}); // dummy node at idx=0 } // build empty tree on [l..r], returns root index int build(int l, int r) { int id = st.size(); st.push_back({0,0,0}); if (l < r) { int m = (l + r) >> 1; st[id].l = build(l, m); st[id].r = build(m+1, r); } return id; } // create new version from prev, add v at pos p int update(int prev, int l, int r, int p, int v) { int id = st.size(); st.push_back(st[prev]); if (l == r) { st[id].sum += v; } else { int m = (l + r) >> 1; if (p <= m) st[id].l = update(st[prev].l, l, m, p, v); else st[id].r = update(st[prev].r, m+1, r, p, v); st[id].sum = st[st[id].l].sum + st[st[id].r].sum; } return id; } // query sum on [ql..qr] int query(int id, int l, int r, int ql, int qr) const { if (!id || qr < l || r < ql) return 0; if (ql <= l && r <= qr) return st[id].sum; int m = (l + r) >> 1; return query(st[id].l, l, m, ql, qr) + query(st[id].r, m+1, r, ql, qr); } }; // solve function to be called by the judge // signature matches: solve(int n, int m, int w, // vector<int> x, vector<int> y, // vector<int> a, vector<int> b, vector<int> c, // vector<int> l, vector<int> r, vector<int> t) long long solve(int n, int m, int w, vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, vector<int> L, vector<int> R, vector<int> T) { // 1) collect all time points for coordinate compression vector<int> allT; allT.reserve(2*m + 2*w + 1); allT.push_back(0); for(int i = 0; i < m; i++){ allT.push_back(a[i]); allT.push_back(b[i]); } for(int i = 0; i < w; i++){ allT.push_back(L[i]); allT.push_back(R[i]); } sort(allT.begin(), allT.end()); allT.erase(unique(allT.begin(), allT.end()), allT.end()); auto comp = [&](int v) { return int(lower_bound(allT.begin(), allT.end(), v) - allT.begin()); }; int Tsz = allT.size(); // 2) bucket meals by compressed R vector<vector<int>> meals_at_r(Tsz); for(int i = 0; i < w; i++){ int lc = comp(L[i]); int rc = comp(R[i]); meals_at_r[rc].push_back(lc); } // 3) build persistent segment tree versions PST pst(Tsz); vector<int> version(Tsz); version[0] = pst.build(0, Tsz-1); for(int lc: meals_at_r[0]){ version[0] = pst.update(version[0], 0, Tsz-1, lc, 1); } for(int i = 1; i < Tsz; i++){ version[i] = version[i-1]; for(int lc: meals_at_r[i]){ version[i] = pst.update(version[i], 0, Tsz-1, lc, 1); } } // helper to get g(b, a): #meals completely inside (b, a) auto get_g = [&](int b, int a) { int bc = comp(b), ac = comp(a); if (ac == 0) return 0; int total = pst.query(version[ac-1], 0, Tsz-1, 0, Tsz-1); int bad = pst.query(version[ac-1], 0, Tsz-1, 0, bc); return total - bad; }; // 4) prepare train indices sorted by departure time vector<int> idx(m); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j){ return a[i] < a[j]; }); // dp[i]: min cost to finish train i vector<ll> dp(m, INF); // for each planet, a min-heap of (arrival_time b_j, train_index j) vector< priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> > heap(n); // and a deque to maintain candidate js with decision-monotonicity vector< deque<int> > dq(n); // initial state: planet 0 at time 0, treat j=-1 with dp=-0 heap[0].push({0, -1}); auto get_dp = [&](int j){ return j < 0 ? 0LL : dp[j]; }; auto get_b = [&](int j){ return j < 0 ? 0 : b[j]; }; ll answer = INF; // 5) main scan in order of departure time for(int _k = 0; _k < m; _k++){ int i = idx[_k]; int p = x[i]; int ai = a[i]; // step1: move all arriving-by-ai trains from heap[p] into dq[p] auto &hp = heap[p]; auto &dq_p = dq[p]; while(!hp.empty() && hp.top().first <= ai){ int j = hp.top().second; hp.pop(); // pop-back by quadrangle-inequality check while(dq_p.size() >= 2){ int j2 = dq_p.back(); int j1 = dq_p[dq_p.size()-2]; ll lhs = get_dp(j2) + (ll)get_g(get_b(j2), ai) * T[p]; ll rhs = get_dp(j1) + (ll)get_g(get_b(j1), ai) * T[p]; if (lhs >= rhs) dq_p.pop_back(); else break; } dq_p.push_back(j); } // step2: front of dq[p] is best predecessor if (!dq_p.empty()){ int j = dq_p.front(); dp[i] = get_dp(j) + (ll)get_g(get_b(j), ai) * T[p] + c[i]; if (y[i] == n-1) answer = min(answer, dp[i]); } // step3: push this train into heap at its arrival planet heap[y[i]].push({ b[i], i }); } if (answer >= INF/2) return -1; return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...