#include<bits/stdc++.h>
using namespace std;
int n,m;
long long inf=1e15,kaf=(1<<20);
struct segment{
long long seg[(1<<21)];
segment(){
for(int i=0;i<(1<<21);i++){
seg[i]=inf;
}
}
void upd(int i,long long w){
if(i==0){
return ;
}
seg[i]=min(seg[i],w);
return upd((i>>1),w);
}
long long pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl){
return inf;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
long long ret=min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
return ret;
}
};
segment seg1,seg2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
long long res=inf;
seg1.upd(kaf+1,0);
seg2.upd(kaf+m,0);
for(int i=0;i<n;i++){
long long l,r,c,w;
cin>>l>>r>>c>>w;
long long fake=seg1.pors(1,0,kaf-1,l,r)+seg2.pors(1,0,kaf-1,l,r);
fake+=w;
res=min(fake,res);
fake=seg1.pors(1,0,kaf-1,l,r);
fake+=w;
seg1.upd(kaf+c,fake);
fake=seg2.pors(1,0,kaf-1,l,r);
fake+=w;
seg2.upd(kaf+c,fake);
}
if(res>=inf){
cout<<-1<<"\n";
}
else{
cout<<res<<'\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 2 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 3 |
Correct |
18 ms |
33108 KB |
Output is correct |
| 4 |
Correct |
16 ms |
33148 KB |
Output is correct |
| 5 |
Correct |
15 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
15 ms |
33148 KB |
Output is correct |
| 7 |
Correct |
15 ms |
33020 KB |
Output is correct |
| 8 |
Correct |
14 ms |
33108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 2 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 3 |
Correct |
18 ms |
33108 KB |
Output is correct |
| 4 |
Correct |
16 ms |
33148 KB |
Output is correct |
| 5 |
Correct |
15 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
15 ms |
33148 KB |
Output is correct |
| 7 |
Correct |
15 ms |
33020 KB |
Output is correct |
| 8 |
Correct |
14 ms |
33108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
33036 KB |
Output is correct |
| 10 |
Runtime error |
39 ms |
66968 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 2 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 3 |
Correct |
18 ms |
33108 KB |
Output is correct |
| 4 |
Correct |
16 ms |
33148 KB |
Output is correct |
| 5 |
Correct |
15 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
15 ms |
33148 KB |
Output is correct |
| 7 |
Correct |
15 ms |
33020 KB |
Output is correct |
| 8 |
Correct |
14 ms |
33108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
33036 KB |
Output is correct |
| 10 |
Runtime error |
39 ms |
66968 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 2 |
Correct |
15 ms |
33108 KB |
Output is correct |
| 3 |
Correct |
18 ms |
33108 KB |
Output is correct |
| 4 |
Correct |
16 ms |
33148 KB |
Output is correct |
| 5 |
Correct |
15 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
15 ms |
33148 KB |
Output is correct |
| 7 |
Correct |
15 ms |
33020 KB |
Output is correct |
| 8 |
Correct |
14 ms |
33108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
33036 KB |
Output is correct |
| 10 |
Runtime error |
39 ms |
66968 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
