Submission #306343

#TimeUsernameProblemLanguageResultExecution timeMemory
306343syyPinball (JOI14_pinball)C++17
100 / 100
705 ms84812 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++) #define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--) typedef pair<ll, ll> pi; typedef pair<pi, pi> pii; #define f first #define s second typedef vector<ll> vi; typedef vector<pi> vpi; typedef vector<pii> vpii; #define pb push_back #define pf push_front #define all(v) v.begin(), v.end() #define INF (ll) 1e9 + 100 #define LLINF (ll) 1e18 #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) ll m, n, a, b, c, d, ans = LLINF; vpii v; vi coord; struct node { ll s, e, m, v; node *l, *r; node(ll S, ll E) { s = S, e = E, m = (s+e)/2, v = LLINF; if (s != e) { l = new node(s, m); r = new node(m+1, e); } } void up(ll x, ll nv) { if (s == e) {v = min(v, nv); return;} else if (x <= m) l->up(x, nv); else r->up(x, nv); v = min(l->v, r->v); } ll query(ll x, ll y) { if (s == x and e == y) return v; else if (y <= m) return l->query(x, y); else if (x > m) return r->query(x, y); else return min(l->query(x, m), r->query(m+1, y)); } } *lseg, *rseg; int main() { fastio; cin >> m >> n; FOR(i, 1, m) { cin >> a >> b >> c >> d; v.pb(pii(pi(a, b), pi(c, d))); coord.pb(a); coord.pb(b); coord.pb(c); } coord.pb(1); coord.pb(n); sort(all(coord)); coord.resize(unique(all(coord)) - coord.begin()); n = coord.size(); lseg = new node(1, coord.size()); rseg = new node(1, coord.size()); for (auto it:v) { a = it.f.f, b = it.f.s, c = it.s.f, d = it.s.s; a = lower_bound(all(coord), a) - coord.begin() + 1; b = lower_bound(all(coord), b) - coord.begin() + 1; c = lower_bound(all(coord), c) - coord.begin() + 1; ll lv = (a == 1 ? 0 : lseg->query(a, b)) + d; ll rv = (b == n ? 0 : rseg->query(a, b)) + d; lseg->up(c, lv); rseg->up(c, rv); ans = min(ans, lv + rv - d); } cout << (ans == LLINF ? -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...