Submission #480154

#TimeUsernameProblemLanguageResultExecution timeMemory
480154hidden1Pinball (JOI14_pinball)C++14
100 / 100
452 ms42184 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 2e15 + 7; #define debug(...) cout << "Line: " << __LINE__ << endl; \ prllDebug(", "#__VA_ARGS__, __VA_ARGS__) template <typename T> void prllDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; } template <typename T, typename... T2> void prllDebug(const char* names, T&& arg1, T2&&... args) { const char* end = strchr(names + 1, ','); cout.write(names + 2, end - names - 2) << " = " << arg1 << endl; prllDebug(end, args...); } const ll MAX_N = 5e5 + 10; struct SegTree { ll tree[4 * MAX_N]; SegTree() { fill(tree, tree + MAX_N * 4, mod); } ll ans(ll curr, ll l, ll r, ll ql, ll qr) { if(ql <= l && r <= qr) { return tree[curr]; } else if(ql > r || l > qr) { return mod; } ll m = (l + r) / 2ll; return min( ans(curr * 2, l, m, ql, qr), ans(curr * 2 + 1, m + 1, r, ql, qr) ); } void upd(ll curr, ll l, ll r, ll ind, ll val) { if(l == r && l == ind) { chkmin(tree[curr], val); return; } else if(l > ind || r < ind) {return;} ll m = (l + r) / 2ll; upd(curr * 2, l, m, ind, val); upd(curr * 2 + 1, m + 1, r, ind, val); tree[curr] = min(tree[curr * 2], tree[curr * 2 + 1]); } }; SegTree lft, rght; struct Comp { vector<ll> start; void push(ll x) { start.push_back(x); } void compress() { sort(start.begin(), start.end()); start.resize(unique(start.begin(), start.end()) - start.begin()); } ll get(ll x) { return lower_bound(start.begin(), start.end(), x) - start.begin(); } }; Comp comp; ll n, m; ll a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N]; signed main() { // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> m >> n; for(ll i = 0; i < m; i ++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; comp.push(a[i]); comp.push(b[i]); comp.push(c[i]); } comp.compress(); ll ans = mod; for(ll i = 0; i < m; i ++) { ll lftBest = lft.ans(1, 0, MAX_N - 1, comp.get(a[i]), comp.get(b[i])); if(a[i] == 1) { lftBest = 0; } lftBest += d[i]; lft.upd(1, 0, MAX_N - 1, comp.get(c[i]), lftBest); ll rghtBest = rght.ans(1, 0, MAX_N - 1, comp.get(a[i]), comp.get(b[i])); if(b[i] == n) { rghtBest = 0; } rghtBest += d[i]; rght.upd(1, 0, MAX_N - 1, comp.get(c[i]), rghtBest); chkmin(ans, lftBest + rghtBest - d[i]); } if(ans == mod) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...