#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz=4e5;
const ll mnv=1e18;
ll s1[sz*2],s2[sz*2];
void update(ll *a,int x,ll v)
{
for(a[x+=sz]=min(a[x],v);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[sz],b[sz],c[sz],d[sz];
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
pinball.cpp: In function 'void update(ll*, int, ll)':
pinball.cpp:9:12: warning: operation on 'x' may be undefined [-Wsequence-point]
for(a[x+=sz]=min(a[x],v);x>1;x>>=1) a[x>>1]=min(a[x],a[x^1]);
~^~~~
pinball.cpp: In function 'int main()':
pinball.cpp:24: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:26: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 time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
