| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1203021 | zeta7532 | 은하철도 (APIO24_train) | C++20 | 0 ms | 0 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 index 0
}
// build an empty tree on [l..r], return root id
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;
}
// point add: create a new version from prev, add v at position 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;
}
// range 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);
}
};
struct Train {
int x, y;
int a, b;
ll c;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, w;
cin >> n >> m >> w;
vector<ll> t(n);
for (int i = 0; i < n; i++) {
cin >> t[i];
}
vector<pair<int,int>> meals(w);
for (int i = 0; i < w; i++) {
cin >> meals[i].first >> meals[i].second;
}
vector<Train> trains(m);
for (int i = 0; i < m; i++) {
cin >> trains[i].x
>> trains[i].y
>> trains[i].a
>> trains[i].b
>> trains[i].c;
}
// 1) 時刻を座標圧縮
vector<int> allT;
allT.reserve(2*m + 2*w + 1);
allT.push_back(0);
for (auto &tr : trains) {
allT.push_back(tr.a);
allT.push_back(tr.b);
}
for (auto &me : meals) {
allT.push_back(me.first);
allT.push_back(me.second);
}
sort(allT.begin(), allT.end());
allT.erase(unique(allT.begin(), allT.end()), allT.end());
auto comp = [&](int x) {
return int(lower_bound(allT.begin(), allT.end(), x) - allT.begin());
};
int Tsz = allT.size();
// 2) meals を r_comp ごとにバケット化
vector<vector<int>> meals_at_r(Tsz);
for (auto &me : meals) {
int lc = comp(me.first);
int rc = comp(me.second);
meals_at_r[rc].push_back(lc);
}
// 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 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) 列車を出発時刻 a の昇順でソートするための idx
vector<int> idx(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(),
[&](int i, int j) { return trains[i].a < trains[j].a; });
// DP, heap, deque の準備
vector<ll> dp(m, INF);
vector< priority_queue<pair<int,int>,
vector<pair<int,int>>, greater<pair<int,int>>> > heap(n);
vector< deque<int> > dq(n);
// 初期状態：planet 0、時刻 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 : trains[j].b);
};
ll ans = INF;
// 5) メインループ
for (int k = 0; k < m; k++) {
int i = idx[k];
int p = trains[i].x;
int ai = trains[i].a;
// step1: 時刻 ai までに到着した j を deque[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
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: 最適な遷移元
if (!dq_p.empty()) {
int j = dq_p.front();
dp[i] = get_dp(j)
+ (ll)get_g(get_b(j), ai) * t[p]
+ trains[i].c;
if (trains[i].y == n - 1)
ans = min(ans, dp[i]);
}
// step3: i を到着 heap に追加
heap[trains[i].y].push({trains[i].b, i});
}
if (ans >= INF / 2) ans = -1;
cout << ans << "\n";
return 0;
}