| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 908899 | Saul0906 | Pinball (JOI14_pinball) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>#define ll long longusing namespace std;ll inf=1e18;struct device{ ll i, a, b, c, d; ll dp[2]={inf, inf}; bool operator<(const device B)const{ return b<B.b; }};struct segtree{ segtree *left, *right; int l, r, mid; ll mn=inf; segtree(int x, int y){ l=x; r=y; mid=(l+r)/2; if(l==r) return; left = new segtree(l,mid); right = new segtree(mid+1,r); } void update(int x, ll dp, bool force=false){ if(x<l || r<x) return; if(x<=l && r<=x){ mn=min(dp,mn); if(force) mn=dp; return; } left->update(x,dp,force); right->update(x,dp,force); mn=min(left->mn,right->mn); } ll query(int x, int y){ if(y<l || r<x) return 1e18; if(x<=l && r<=y) return mn; return min(left->query(x,y),right->query(x,y)); }};int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; vector<device> devs(n); ll ans=1e18; map<int, int> ccmp; set<int> nums; for(int i=0; i<n; i++){ cin>>devs[i].a>>devs[i].b>>devs[i].c>>devs[i].d; devs[i].i=i; nums.insert(devs[i].a); nums.insert(devs[i].b); nums.insert(devs[i].c); } nums.insert(m); int x=0; for(auto e:nums) ccmp[e]=x++; segtree ST(0,x), ST2(0,x); ST.update(0,0); for(int i=0; i<n; i++){ devs[i].a=ccmp[devs[i].a]; devs[i].b=ccmp[devs[i].b]; devs[i].c=ccmp[devs[i].c]; } for(int i=0; i<n; i++){ devs[i].dp[0]=ST.query(devs[i].a,devs[i].b)+devs[i].d; ST.update(devs[i].c,devs[i].dp[0]); } ST2.update(x-1,0); for(int i=0; i<n; i++){ devs[i].dp[1]=ST2.query(devs[i].a,devs[i].b)+devs[i].d; ST2.update(devs[i].c,devs[i].dp[1]); ans=min(ans,devs[i].dp[1]+devs[i].dp[0]-devs[i].d); //cout<<devs[i].a<<" "<<devs[i].b<<" "<<devs[i].c<<" "<<devs[i].dp[0]<<" "<<devs[i].dp[1]<<endl; } if(ans==inf) cout<<-1<<endl; else cout<<ans<<endl;}