Submission #117362

#TimeUsernameProblemLanguageResultExecution timeMemory
117362Adhyyan1252Pinball (JOI14_pinball)C++11
100 / 100
385 ms16136 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define INF 1e16 //825 struct segtree{ vector<int> t; int sz; segtree(int size){ sz = size; t = vector<int>(4*size, INF); } void upd(int i, int s, int e, int indx, int val){ if(s == e){ t[i] = min(val, t[i]); return; } int m = (s + e)/2; if(indx <= m){ upd(i*2, s, m, indx, val); }else{ upd(i*2+1, m+1, e, indx, val); } t[i] = min(t[i*2], t[i*2+1]); } int query(int i, int s, int e, int l, int r){ if(l > r) return INF; if(l <= s && e <= r) return t[i ]; if(s > r || e < l) return INF; int m = (s + e)/2; return min(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r)); } }; signed main(){ int n, m; cin>>m>>n; vector<int> a, b, c, d; a.resize(m); b.resize(m); c.resize(m); d.resize(m); for(int i = 0; i < m; i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; } vector<pair<int, int> > lc, rc; for(int i = 0; i < m; i++){ lc.push_back({c[i], i}); } sort(lc.begin(), lc.end()); vector<int> lindx(m); for(int i = 0; i < m; i++){ lindx[lc[i].second] = i; } segtree left(m), right(m); int ans = INF; for(int i = 0; i < m; i++){ //upd this device now //the index is lindx[i] //find the range of vertices for query //do binary search on lc array with a, b pair<int, int> ls = {a[i], -1}; pair<int, int> rs = {b[i], INF}; int l = lower_bound(lc.begin(), lc.end(),ls)-lc.begin(); int r = upper_bound(lc.begin(), lc.end(),rs)-lc.begin()-1; //cout<<"RANGE: "<<i<<" : "<<lindx[i]<<" "<<l<<" "<<r<<endl; int Lnval = left.query(1, 0, left.sz-1, l, r) + d[i]; if(a[i] == 1) Lnval = d[i]; left.upd(1, 0, left.sz-1, lindx[i], Lnval); int Rnval = right.query(1, 0, right.sz-1, l, r) + d[i]; if(b[i] == n) Rnval = d[i]; right.upd(1, 0, right.sz-1, lindx[i], Rnval); ans = min(ans, Lnval + Rnval - d[i]); //cout<<i<<": "<<Lnval<<" "<<Rnval<<endl; } if(ans >= INF) cout<<-1<<endl; else cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...