Submission #1013164

#TimeUsernameProblemLanguageResultExecution timeMemory
1013164PanndaPinball (JOI14_pinball)C++17
100 / 100
171 ms15424 KiB
#include <bits/stdc++.h> using namespace std; // supports: point modify, range apply, range query, walk to find first/last with some precedent // you are to implement the 2 structs Tag and Info // for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element template<class Info, class Tag> struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); } template<class T> LazySegmentTree(vector<T> init_) { init(init_); } void init(int n_, Info v_ = Info()) { init(vector<Info>(n_, v_)); } template<class T> void init(vector<T> init_) { n = init_.size(); info.assign(4 << __lg(n), Info()); tag.assign(4 << __lg(n), Tag()); function<void(int, int, int)> build = [&](int p, int l, int r) { if (r - l == 1) { info[p] = init_[l]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; } void apply(int p, const Tag &v) { info[p].apply(v); tag[p].apply(v); } void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); } void modify(int p, int l, int r, int x, const Info &v) { if (r - l == 1) { info[p] = v; return; } int m = (l + r) / 2; push(p); if (x < m) { modify(2 * p, l, m, x, v); } else { modify(2 * p + 1, m, r, x, v); } pull(p); } void modify(int p, const Info &v) { modify(1, 0, n, p, v); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l >= y || r <= x) { return Info(); } if (l >= x && r <= y) { return info[p]; } int m = (l + r) / 2; push(p); return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y); } Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); } void rangeApply(int p, int l, int r, int x, int y, const Tag &v) { if (l >= y || r <= x) { return; } if (l >= x && r <= y) { apply(p, v); return; } int m = (l + r) / 2; push(p); rangeApply(2 * p, l, m, x, y, v); rangeApply(2 * p + 1, m, r, x, y, v); pull(p); } void rangeApply(int l, int r, const Tag &v) { return rangeApply(1, 0, n, l, r, v); } template<class F> int findFirst(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findFirst(2 * p, l, m, x, y, pred); if (res == -1) { res = findFirst(2 * p + 1, m, r, x, y, pred); } return res; } template<class F> int findFirst(int l, int r, F &&pred) { return findFirst(1, 0, n, l, r, pred); } template<class F> int findLast(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findLast(2 * p + 1, m, r, x, y, pred); if (res == -1) { res = findLast(2 * p, l, m, x, y, pred); } return res; } template<class F> int findLast(int l, int r, F &&pred) { return findLast(1, 0, n, l, r, pred); } }; const long long INF = 1e18; struct Tag { long long mn = INF; void apply(const Tag &t) & { mn = min(mn, t.mn); } }; struct Info { long long mn = INF; void apply(const Tag &t) & { mn = min(mn, t.mn); } Info operator+(const Info &b) { return {min(mn, b.mn)}; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> l(n), r(n), drop(n), cost(n); for (int i = 0; i < n; i++) { cin >> l[i] >> r[i] >> drop[i] >> cost[i]; } vector<int> points = {1, m}; points.insert(points.end(), drop.begin(), drop.end()); sort(points.begin(), points.end()); points.resize(unique(points.begin(), points.end()) - points.begin()); const int C = points.size(); for (int i = 0; i < n; i++) { l[i] = lower_bound(points.begin(), points.end(), l[i]) - points.begin(); r[i] = lower_bound(points.begin(), points.end(), r[i] + 1) - points.begin(); drop[i] = lower_bound(points.begin(), points.end(), drop[i]) - points.begin(); } LazySegmentTree<Info, Tag> seg_l(C); seg_l.modify(0, {0}); LazySegmentTree<Info, Tag> seg_r(C); seg_r.modify(C - 1, {0}); long long ans = INF; for (int i = 0; i < n; i++) { long long get_l = seg_l.rangeQuery(l[i], r[i]).mn; long long get_r = seg_r.rangeQuery(l[i], r[i]).mn; ans = min(ans, get_l + get_r + cost[i]); seg_l.rangeApply(drop[i], drop[i] + 1, {cost[i] + get_l}); seg_r.rangeApply(drop[i], drop[i] + 1, {cost[i] + get_r}); } if (ans == INF) ans = -1; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...