Submission #896515

#TimeUsernameProblemLanguageResultExecution timeMemory
896515AiperiiiPinball (JOI14_pinball)C++14
100 / 100
701 ms58956 KiB
#include <bits/stdc++.h> #define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back using namespace std; const int N=3e5+5; int l[N*4],r[N*4]; map <int,int> val_ind; void build(int v,int tl,int tr){ if(tl==tr){ l[v]=1e16; r[v]=1e16; } else{ int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); l[v]=min(l[v*2],l[v*2+1]); r[v]=min(r[v*2],r[v*2+1]); } } int get_min_l(int v,int tl,int tr,int L,int R){ if(tr<L or R<tl)return 1e18; if(L<=tl && tr<=R)return l[v]; int tm=(tl+tr)/2; return min(get_min_l(v*2,tl,tm,L,R), get_min_l(v*2+1,tm+1,tr,L,R)); } int get_min_r(int v,int tl,int tr,int L,int R){ if(tr<L or R<tl)return 1e18; if(L<=tl && tr<=R)return r[v]; int tm=(tl+tr)/2; return min(get_min_r(v*2,tl,tm,L,R), get_min_r(v*2+1,tm+1,tr,L,R)); } void update_l(int v,int tl,int tr,int pos,int val){ if(tl==tr)l[v]=min(val,l[v]); else{ int tm=(tl+tr)/2; if(pos<=tm)update_l(v*2,tl,tm,pos,val); else update_l(v*2+1,tm+1,tr,pos,val); l[v]=min(l[v*2],l[v*2+1]); } } void update_r(int v,int tl,int tr,int pos,int val){ if(tl==tr)r[v]=min(val,r[v]); else{ int tm=(tl+tr)/2; if(pos<=tm)update_r(v*2,tl,tm,pos,val); else update_r(v*2+1,tm+1,tr,pos,val); r[v]=min(r[v*2],r[v*2+1]); } } signed main(){ ios_base::sync_with_stdio(); cin.tie(0); int m,T; cin>>m>>T; vector <int> a(m),b(m),c(m),d(m); set <int> st; st.insert(1);st.insert(T); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; st.insert(a[i]); st.insert(b[i]); st.insert(c[i]); } int cnt=1; for(auto x : st){ val_ind[x]=cnt; cnt++; } int n=st.size(); build(1,1,n); int ans=1e16; for(int i=0;i<m;i++){ int res=0; if(a[i]==1){ res+=d[i]; update_l(1,1,n,val_ind[c[i]],d[i]); } else{ int x=get_min_l(1,1,n,val_ind[a[i]],val_ind[b[i]]); res+=x;res+=d[i]; update_l(1,1,n,val_ind[c[i]],x+d[i]); } if(b[i]==T){ res+=d[i]; update_r(1,1,n,val_ind[c[i]],d[i]); } else{ int x=get_min_r(1,1,n,val_ind[a[i]],val_ind[b[i]]); res+=x;res+=d[i]; update_r(1,1,n,val_ind[c[i]],x+d[i]); } ans=min(ans,res-d[i]); } if(ans==1e16)ans=-1; cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...