Submission #380494

#TimeUsernameProblemLanguageResultExecution timeMemory
380494pure_memPinball (JOI14_pinball)C++14
11 / 100
395 ms6380 KiB
#include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 1e5 + 12, M = 1e9; const ll INF = 1e18; struct node{ node *l, *r; ll val = INF; }; int n, m, dp[N], p[N]; ll cL[N], cR[N]; void upd(node *v, int tl, int tr, int pos, ll val){ if(tl > pos || pos > tr) return; if(tl == tr){ v->val = min(v->val, val); return; } int tm = (tl + tr) / 2; if(!v->l) v->l = new node(); if(!v->r) v->r = new node(); upd(v->l, tl, tm, pos, val); upd(v->r, tm + 1, tr, pos, val); v->val = min(v->l->val, v->r->val); } ll get(node *v, int tl, int tr, int l, int r){ if(tl > r || l > tr || !v) return INF; if(tl >= l && tr <= r) return v->val; int tm = (tl + tr) / 2; return min(get(v->l, tl, tm, l, r), get(v->r, tm + 1, tr, l, r)); } int main () { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> m >> n; ll ans = INF; node* root1 = new node(); node* root2 = new node(); for(int i = 1;i <= n;i++){ int l, r, c, cost; cin >> l >> r >> c >> cost; cL[i] = get(root1, 1, n, l, r) + cost; if(l == 1) cL[i] = cost; cR[i] = get(root2, 1, n, l, r) + cost; if(r == n) cR[i] = cost; ans = min(ans, cL[i] + cR[i] - cost); upd(root1, 1, n, c, cL[i]); upd(root2, 1, n, c, cR[i]); } if(ans == INF) ans = -1; cout << 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...