Submission #887152

#TimeUsernameProblemLanguageResultExecution timeMemory
887152maxFedorchukPinball (JOI14_pinball)C++14
0 / 100
1 ms4444 KiB
#include<bits/stdc++.h> using namespace std; const long long MX=3e5+10; const long long INF=1e18; long long mas[2][4*MX]; void build(long long v,long long tl,long long tr) { mas[0][v]=INF; mas[1][v]=INF; if(tl==tr) { return; } long long mid=(tl+tr)/2; build(v*2,tl,mid); build(v*2+1,mid+1,tr); return; } long long get_mn(long long in,long long v,long long tl,long long tr,long long l,long long r) { if(l<=tl && tr<=r) { return mas[in][v]; } if(tr<l || r<tl) { return INF; } long long mid=(tl+tr)/2; return min(get_mn(in,v*2,tl,mid,l,r),get_mn(in,v*2+1,mid+1,tr,l,r)); } void upd(long long in,long long v,long long tl,long long tr,long long pos,long long zn) { if(tl==tr) { mas[in][v]=zn; return; } long long mid=(tl+tr)/2; if(pos<=mid) { upd(in,v*2,tl,mid,pos,zn); } else { upd(in,v*2+1,mid+1,tr,pos,zn); } mas[in][v]=min(mas[in][v*2],mas[in][v*2+1]); return; } long long m,n; pair < pair < long long , long long > , pair < long long , long long > > zap[MX]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); map < long long , long long > mp; cin>>m>>n; for(long long i=1;i<=m;i++) { cin>>zap[i].first.first>>zap[i].first.second>>zap[i].second.first>>zap[i].second.second; mp[zap[i].first.first]=1; mp[zap[i].first.second]=1; mp[zap[i].second.first]=1; } mp[1]=1; mp[n]=1; long long uk=0; for(auto & u:mp) { uk++; u.second=uk; } n=uk; build(1,1,n); upd(0,1,1,n,1,0); upd(1,1,1,n,n,0); long long res=INF; for(long long i=1;i<=m;i++) { zap[i].first.first=mp[zap[i].first.first]; zap[i].first.second=mp[zap[i].first.second]; zap[i].second.first=mp[zap[i].second.first]; res=min(res,get_mn(0,1,1,n,zap[i].first.first,zap[i].first.second)+get_mn(1,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second); upd(0,1,1,n,zap[i].second.first,min(INF,get_mn(0,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second)); upd(1,1,1,n,zap[i].second.first,min(INF,get_mn(1,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second)); } if(res==INF) { res=-1; } cout<<res<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...