Submission #53831

#TimeUsernameProblemLanguageResultExecution timeMemory
53831TadijaSebezPinball (JOI14_pinball)C++11
100 / 100
934 ms35020 KiB
#include <stdio.h> #include <map> #include <algorithm> #include <vector> using namespace std; #define ll long long const int N=200050; const int M=32*N*2; const ll inf=1e18; int ls[M],rs[M],tsz,root,root2;ll Min[M]; void Set(int &c, int ss, int se, int qi, ll val) { if(!c) c=++tsz,Min[c]=val; Min[c]=min(Min[c],val); if(ss==se) return; int mid=ss+se>>1; if(qi<=mid) Set(ls[c],ss,mid,qi,val); else Set(rs[c],mid+1,se,qi,val); } ll Get(int c, int ss, int se, int qs, int qe) { if(qs>se || ss>qe || qs>qe) return inf; if(qs<=ss && qe>=se) return Min[c]; int mid=ss+se>>1; return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe)); } map<int,ll> dp1,dp2; int a[N],b[N],c[N]; ll d1[N],d2[N],d[N]; vector<int> id; int Find(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;} int Upper(int x){ return upper_bound(id.begin(),id.end(),x)-id.begin();} int main() { Min[0]=inf; int n,m,i; scanf("%i %i",&n,&m); for(i=1;i<=n;i++) scanf("%i %i %i %lld",&a[i],&b[i],&c[i],&d[i]),dp1[c[i]]=dp2[c[i]]=inf,d1[i]=d2[i]=inf,id.push_back(c[i]); sort(id.begin(),id.end()); for(i=1;i<=n;i++) { ll y; if(a[i]==1) { ll x=dp1[c[i]];y=d[i]; dp1[c[i]]=min(x,y); Set(root,1,m,Find(c[i]),d[i]); } else { ll x=dp1[c[i]];y=Get(root,1,m,Find(a[i]),Upper(b[i]))+d[i]; dp1[c[i]]=min(x,y); Set(root,1,m,Find(c[i]),dp1[c[i]]); } d1[i]=y; } for(i=1;i<=n;i++) { ll y; if(b[i]==m) { ll x=dp2[c[i]];y=d[i]; dp2[c[i]]=min(x,y); Set(root2,1,m,Find(c[i]),d[i]); } else { ll x=dp2[c[i]];y=Get(root2,1,m,Find(a[i]),Upper(b[i]))+d[i]; dp2[c[i]]=min(x,y); Set(root2,1,m,Find(c[i]),dp2[c[i]]); } d2[i]=y; } ll sol=inf; for(i=1;i<=n;i++) sol=min(sol,dp1[c[i]]+dp2[c[i]]),sol=min(sol,d1[i]+d2[i]-d[i]); if(sol>=inf) printf("-1\n"); else printf("%lld\n",sol); //for(i=1;i<=n;i++) printf("%lld %lld\n",d1[i],d2[i]); return 0; }

Compilation message (stderr)

pinball.cpp: In function 'void Set(int&, int, int, int, long long int)':
pinball.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
pinball.cpp: In function 'long long int Get(int, int, int, int, int)':
pinball.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:38:109: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%i %i %i %lld",&a[i],&b[i],&c[i],&d[i]),dp1[c[i]]=dp2[c[i]]=inf,d1[i]=d2[i]=inf,id.push_back(c[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...