Submission #820013

#TimeUsernameProblemLanguageResultExecution timeMemory
820013winter0101Pinball (JOI14_pinball)C++14
0 / 100
1 ms212 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> #define pll pair<long long,long long> #define eb emplace_back const long long inf=1e14+9; const int maxn=1e5+9; struct IT{ vector<long long>st; void build(int id,int l,int r){ st[id]=inf; if (l==r)return; int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); } void resz(int n){ st.resize(4*n+9); build(1,1,n); } void update(int id,int l,int r,int u,long long val){ if (l>u||r<u)return; if (l==r){ st[id]=min(st[id],val); return; } int mid=(l+r)/2; update(id*2,l,mid,u,val); update(id*2+1,mid+1,r,u,val); st[id]=min(st[id*2],st[id*2+1]); } long long get(int id,int l,int r,int u,int v){ if (l>v||r<u||u>v)return inf; if (u<=l&&r<=v)return st[id]; int mid=(l+r)/2; return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v)); } }; struct pin{ int x,y,z; long long t; }a[maxn]; int m,n; void nen(){ vector<int>t; t.pb(1),t.pb(n),t.pb(0); for1(i,1,m){ t.pb(a[i].x); t.pb(a[i].y); t.pb(a[i].z); } sort(all(t)); map<int,int>d; for1(i,1,sz(t)-1){ if (t[i]==t[i-1])continue; d[t[i]]=d[t[i-1]]+1; n=d[t[i]]; } for1(i,1,m){ a[i].x=d[a[i].x],a[i].y=d[a[i].y],a[i].z=d[a[i].z]; } } void solve(){ IT st1,st2; st1.resz(n),st2.resz(n); long long ans=inf; for1(i,1,m){ ans=min(ans,a[i].t+st1.get(1,1,n,a[i].x,a[i].y)+st2.get(1,1,n,a[i].x,a[i].y)); long long v1=a[i].t+st1.get(1,1,n,a[i].x,a[i].y); if (a[i].x==1)v1=a[i].t; long long v2=a[i].t+st2.get(1,1,n,a[i].x,a[i].y); if (a[i].y==n)v2=a[i].t; st1.update(1,1,n,a[i].z,v1),st2.update(1,1,n,a[i].z,v2); //cout<<i<<" "<<v1<<" "<<v2<<'\n'; } if (ans>=inf)ans=-1; cout<<ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); cin>>m>>n; for1(i,1,m)cin>>a[i].x>>a[i].y>>a[i].z>>a[i].t; nen(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...