제출 #991409

#제출 시각아이디문제언어결과실행 시간메모리
991409SanguineChameleon은하철도 (APIO24_train)C++17
5 / 100
1078 ms18520 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; const int lim = 1e9 + 20; const int inf1 = 1e9 + 20; const long long inf2 = 1e18L + 20; struct planet { int L, R; long long cost; planet(long long _cost): L(-1), R(-2), cost(_cost) {}; }; struct train { int L, R, u, v; long long cost; train(int _L, int _R, int _u, int _v, long long _cost): L(_L), R(_R), u(_u), v(_v), cost(_cost) {}; }; struct meal { int L, R; meal(int _L, int _R): L(_L), R(_R) {}; }; struct event { int time, type, id; event(int _time, int _type, int _id): time(_time), type(_type), id(_id) {}; }; bool operator<(train &t1, train &t2) { if (t1.v != t2.v) { return t1.v < t2.v; } else { return t1.R < t2.R; } } bool operator<(meal &m1, meal &m2) { return m1.L > m2.L; } bool operator<(event &e1, event &e2) { if (e1.time != e2.time) { return e1.time < e2.time; } else { return e1.type < e2.type; } } bool operator<(meal &m, int x) { return m.L > x; } bool operator<(train &t, int x) { return t.R <= x; } struct fenwick_tree { vector<int> sum; int N; fenwick_tree(int _N) { N = _N; sum.resize(N + 1); } void update(int pos) { pos++; for (int i = pos; i <= N; i += i & (-i)) { sum[i]++; } } int get(int pos) { pos++; int res = 0; for (int i = pos; i > 0; i -= i & (-i)) { res += sum[i]; } return res; } }; struct segment_tree { struct node { long long min; long long lazy; node(): min(inf2), lazy(0) {}; }; vector<node> tree; int N; segment_tree(int _N) { N = _N; tree.resize(N << 2); } void shift(int id, long long delta) { tree[id].min += delta; tree[id].lazy += delta; } void push(int id) { shift(id << 1, tree[id].lazy); shift(id << 1 | 1, tree[id].lazy); tree[id].lazy = 0; } void merge(int id) { tree[id].min = min(tree[id << 1].min, tree[id << 1 | 1].min); } void update_pos(int id, int tl, int tr, int pos, long long val) { if (tl == tr) { tree[id].min = val; tree[id].lazy = 0; return; } push(id); int tm = (tl + tr) >> 1; if (pos <= tm) { update_pos(id << 1, tl, tm, pos, val); } else { update_pos(id << 1 | 1, tm + 1, tr, pos, val); } merge(id); } void update_range(int id, int tl, int tr, int ql, int qr, long long delta) { if (tl == ql && tr == qr) { shift(id, delta); return; } push(id); int tm = (tl + tr) >> 1; if (qr <= tm) { update_range(id << 1, tl, tm, ql, qr, delta); } else if (ql >= tm + 1) { update_range(id << 1 | 1, tm + 1, tr, ql, qr, delta); } else { update_range(id << 1, tl, tm, ql, tm, delta); update_range(id << 1 | 1, tm + 1, tr, tm + 1, qr, delta); } merge(id); } long long get_range(int id, int tl, int tr, int ql, int qr) { if (tl == ql && tr == qr) { return tree[id].min; } push(id); int tm = (tl + tr) >> 1; if (qr <= tm) { return get_range(id << 1, tl, tm, ql, qr); } else if (ql >= tm + 1) { return get_range(id << 1 | 1, tm + 1, tr, ql, qr); } else { return min(get_range(id << 1, tl, tm, ql, tm), get_range(id << 1 | 1, tm + 1, tr, tm + 1, qr)); } } void update_pos(int pos, long long val) { pos++; update_pos(1, 1, N, pos, val); } void update_range(int l, int r, long long delta) { if (l > r) { return; } l++; r++; update_range(1, 1, N, l, r, delta); } long long get_range(int l, int r) { if (l > r) { return inf2; } l++; r++; return min(get_range(1, 1, N, l, r), inf2); } }; long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) { vector<planet> planets; for (int i = 0; i < N; i++) { planets.emplace_back(T[i]); } int planet_cnt = planets.size(); vector<train> trains; for (int i = 0; i < M; i++) { trains.emplace_back(A[i], B[i], X[i], Y[i], C[i]); } trains.emplace_back(-1, 0, 0, 0, 0); trains.emplace_back(inf1, inf1 + 1, planet_cnt - 1, planet_cnt - 1, 0); sort(trains.begin(), trains.end()); int train_cnt = trains.size(); for (int i = 0; i < train_cnt; i++) { if (i == 0 || trains[i].v != trains[i - 1].v) { planets[trains[i].v].L = i; } if (i == train_cnt - 1 || trains[i].v != trains[i + 1].v) { planets[trains[i].v].R = i; } } vector<meal> meals; for (int i = 0; i < W; i++) { meals.emplace_back(L[i], R[i]); } sort(meals.begin(), meals.end()); int meal_cnt = meals.size(); vector<event> events; for (int id = 0; id < train_cnt; id++) { events.emplace_back(trains[id].L, 0, id); } for (int id = 0; id < meal_cnt; id++) { events.emplace_back(meals[id].R, 1, id); } sort(events.begin(), events.end()); vector<bool> is_heavy(planet_cnt); for (int i = 0; i < planet_cnt; i++) { is_heavy[i] = (planets[i].R - planets[i].L + 1) > lim; } vector<int> heavy; for (int i = 0; i < planet_cnt; i++) { if (is_heavy[i]) { heavy.push_back(i); } } vector<long long> dp(train_cnt, inf2); fenwick_tree fen(meal_cnt); segment_tree seg(train_cnt); for (auto &e: events) { int type = e.type; int id = e.id; if (type == 0) { int u = trains[id].u; if (id == 0) { dp[id] = 0; } else { if (is_heavy[u]) { int pos = lower_bound(trains.begin() + planets[u].L, trains.begin() + planets[u].R + 1, trains[id].L) - trains.begin() - 1; dp[id] = seg.get_range(planets[u].L, pos) + trains[id].cost; } else { for (int i = planets[u].L; i <= planets[u].R; i++) { if (trains[i].R > trains[id].L) { break; } int pos = lower_bound(meals.begin(), meals.end(), trains[i].R) - meals.begin() - 1; dp[id] = min(dp[id], dp[i] + planets[u].cost * fen.get(pos) + trains[id].cost); } } } if (is_heavy[u]) { seg.update_pos(id, dp[id]); } } else { fen.update(id); for (auto u: heavy) { int pos = lower_bound(trains.begin() + planets[u].L, trains.begin() + planets[u].R + 1, meals[id].L - 1) - trains.begin() - 1; seg.update_range(planets[u].L, pos, planets[u].cost); } } } long long res = dp.back(); if (res == inf2) { res = -1; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...