#include <stdio.h>
#include <map>
#include <algorithm>
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) 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];
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;
for(i=n;i>=1;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,c[i],d[i]);
}
else
{
ll x=dp1[c[i]];y=Get(root,1,m,a[i],b[i])+d[i];
dp1[c[i]]=min(x,y);
Set(root,1,m,c[i],dp1[c[i]]);
}
d1[i]=y;
}
for(i=n;i>=1;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,c[i],d[i]);
}
else
{
ll x=dp2[c[i]];y=Get(root2,1,m,a[i],b[i])+d[i];
dp2[c[i]]=min(x,y);
Set(root2,1,m,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);
return 0;
}
Compilation message
pinball.cpp: In function 'void Set(int&, int, int, int, long long int)':
pinball.cpp:15: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:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:33: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:34:93: 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;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
