Submission #53081

#TimeUsernameProblemLanguageResultExecution timeMemory
53081okaybody10Pinball (JOI14_pinball)C++98
100 / 100
275 ms16104 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int sz=4e5+3; const ll mnv=1e18; ll s1[sz*2],s2[sz*2]; void update(ll *a,int x,ll v) { x+=sz; a[x]=min(a[x],v); for(;x>1;x>>=1) a[x>>1]=min(a[x],a[x^1]); } ll query(ll *a,int s,int e) { ll ans=mnv; for(s+=sz,e+=sz;s<e;s>>=1,e>>=1) { if(s&1) ans=min(ans,a[s++]); if(e&1) ans=min(ans,a[--e]); } return ans; } int main() { int N,M; scanf("%d %d",&N,&M); int a[100006],b[100006],c[100006],d[100006]; for(int i=0;i<N;i++) scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]); vector<int> e; e.push_back(1),e.push_back(M); for(int i=0;i<N;i++) e.push_back(a[i]),e.push_back(b[i]),e.push_back(c[i]); sort(e.begin(),e.end()); vector<int>::iterator it; it=unique(e.begin(),e.end()); e.resize(distance(e.begin(),it)); for(int i=0;i<N;i++) a[i]=lower_bound(e.begin(),e.end(),a[i])-e.begin(),b[i]=lower_bound(e.begin(),e.end(),b[i])-e.begin(),c[i]=lower_bound(e.begin(),e.end(),c[i])-e.begin(); for(int i=0;i<sz*2;i++) s1[i]=s2[i]=mnv; ll ans=mnv; int cnt=e.size(); update(s1,0,0),update(s2,cnt-1,0); for(int i=0;i<N;i++) { ll o1=query(s1,a[i],b[i]+1)+d[i]; update(s1,c[i],o1); ll o2=query(s2,a[i],b[i]+1)+d[i]; update(s2,c[i],o2); ans=min(ans,o1+o2-d[i]); } return !printf("%lld",ans==mnv ? -1 : ans); }

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<N;i++) scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...