| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1203025 | zeta7532 | Train (APIO24_train) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (1LL<<60);
// Persistent Segment Tree（点追加・区間和）
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}); // ダミー
}
// [l..r] で空の木を構築し root を返す
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;
}
// prev をコピーして pos p に値 v を足した新バージョンを作って返す
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;
}
// id 版の木から [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 関数だけを定義
// signature: solve(n, m, w, t, x, y, a, b, c, L, R)
long long solve(int n, int m, int w,
const vector<int> &t,
const vector<int> &x,
const vector<int> &y,
const vector<int> &a,
const vector<int> &b,
const vector<int> &c,
const vector<int> &L,
const vector<int> &R) {
// 1) 全時刻を集めて座標圧縮
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) meals を r_comp ごとにバケット化
vector<vector<int>> meals_at_r(Tsz);
for(int i=0;i<w;i++){
meals_at_r[ comp(R[i]) ].push_back( comp(L[i]) );
}
// 3) 永続セグ木のバージョン構築
PST pst(Tsz);
vector<int> version(Tsz);
version[0] = pst.build(0, Tsz-1);
for(int lpos: meals_at_r[0]){
version[0] = pst.update(version[0], 0, Tsz-1, lpos, 1);
}
for(int i=1;i<Tsz;i++){
version[i] = version[i-1];
for(int lpos: meals_at_r[i]){
version[i] = pst.update(version[i], 0, Tsz-1, lpos, 1);
}
}
// g(b,a) = 区間 (b,a) に完全に含まれる meal の数
auto get_g = [&](int bval, int aval){
int bc = comp(bval), ac = comp(aval);
if(ac == 0) return 0;
int tot = pst.query(version[ac-1], 0, Tsz-1, 0, Tsz-1);
int bad = pst.query(version[ac-1], 0, Tsz-1, 0, bc);
return tot - bad;
};
// 4) 列車を出発時刻 a の昇順で一度だけ走査するための順序
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 本体
vector<ll> dp(m, INF);
// 各惑星ごとに到着候補を管理する min-heap と deque
vector< priority_queue<pair<int,int>,
vector<pair<int,int>>, greater<pair<int,int>>> > heap(n);
vector< deque<int> > dq(n);
// 初期状態：planet 0 に時刻0, j=-1
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) departure 時刻昇順で列車 i を処理
for(int _k=0; _k<m; _k++){
int i = idx[_k];
int p = x[i], ai = a[i];
auto &hp = heap[p];
auto &dq_p = dq[p];
// step1: 到着済み j を heap[p] から dq[p] へ
while(!hp.empty() && hp.top().first <= ai){
int j = hp.top().second; hp.pop();
// pop-back by quadrangle-inequality
while(dq_p.size()>=2){
int j2 = dq_p.back(), 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: dq_p.front() が最適 j*
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: この i を到着 heap に enqueue
heap[y[i]].push({b[i], i});
}
if(answer >= INF/2) return -1;
return answer;
}