Submission #856982

#TimeUsernameProblemLanguageResultExecution timeMemory
856982thanh913Pinball (JOI14_pinball)C++14
100 / 100
179 ms31644 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define int long long const int N = 1e5+5; struct interval { int l, r, pos, cost; }; //------------------------------- interval a[N]; int n, len; vector<int> vals; struct SegmentTree { ll seg[N*12]; SegmentTree() { memset(seg, 0x3f, sizeof(seg)); } void update(int pos, ll val, int l = 0, int r = vals.size() - 1, int id = 1) { if (l > pos || r < pos) return; if (l == r) { seg[id] = min(seg[id], val); return; } int mid = (l+r) / 2; update(pos, val, l, mid, id*2); update(pos, val, mid+1, r, id*2 + 1); seg[id] = min(seg[id*2], seg[id*2 + 1]); } ll get(int u, int v, int l = 0, int r = vals.size() - 1, int id = 1) { if (l > v || r < u) return 4e18; if (l >= u && r <= v) return seg[id]; int mid = (l+r) / 2; return min(get(u, v, l, mid, id*2), get(u, v, mid+1, r, id*2 + 1)); } } lTree, rTree; int idx(int val) { return lower_bound(vals.begin(), vals.end(), val) - vals.begin(); }; signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> len; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r >> a[i].pos >> a[i].cost; vals.push_back(a[i].l); vals.push_back(a[i].r); vals.push_back(a[i].pos); } vals.push_back(1); vals.push_back(len); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 1; i <= n; i++) { a[i].l = idx(a[i].l); a[i].r = idx(a[i].r); a[i].pos = idx(a[i].pos); } ll ans = 4e18; lTree.update(idx(1), 0); rTree.update(idx(len), 0); for (int i = 1; i <= n; i++) { ll v1 = lTree.get(a[i].l, a[i].r) + a[i].cost; ll v2 = rTree.get(a[i].l, a[i].r) + a[i].cost; ans = min(ans, v1+v2 - a[i].cost); lTree.update(a[i].pos, v1); rTree.update(a[i].pos, v2); } cout << (ans > 1e18 ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...