#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
const ll LINF=(1LL<<60)-1LL;
struct Segtree{
int n;
vector<ll> dat;
Segtree(int n_){
n=1;
while(n<n_){
n<<=1;
}
dat.resize(2*n,LINF);
}
void upd(int k,ll x){
k+=n;
dat[k]=min(dat[k],x);
k>>=1;
while(k>0){
dat[k]=min(dat[k<<1],dat[k<<1|1]);
k>>=1;
}
}
ll get(int a,int b,int k,int l,int r){
if(b<=l||r<=a){
return LINF;
}
if(a<=l&&r<=b){
return dat[k];
}
return min(get(a,b,k<<1,l,(l+r)>>1),get(a,b,k<<1|1,(l+r)>>1,r));
}
ll get(int a,int b){
return get(a,b,1,0,n);
}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int m,nn;cin>>m>>nn;
vector<ll> a(m),b(m),c(m),d(m),v;
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
v.push_back(a[i]);
v.push_back(b[i]);
v.push_back(c[i]);
}
v.push_back(1);
v.push_back(nn);
sort(all(v));
v.erase(unique(all(v)),v.end());
int n=v.size();
for(int i=0;i<m;i++){
a[i]=lower_bound(all(v),a[i])-v.begin();
b[i]=lower_bound(all(v),b[i])-v.begin();
c[i]=lower_bound(all(v),c[i])-v.begin();
}
ll res=LINF;
Segtree seg1(n+1),seg2(n+1);
seg1.upd(0,0);
seg2.upd(n-1,0);
for(int i=0;i<m;i++){
ll s1=seg1.get(a[i],b[i]+1),s2=seg2.get(a[i],b[i]+1);
s1+=d[i];
s2+=d[i];
res=min(res,s1+s2-d[i]);
seg1.upd(c[i],s1);
seg2.upd(c[i],s2);
}
if(res==LINF){
cout<<-1<<endl;
return 0;
}
cout<<res<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
4 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
4 ms |
636 KB |
Output is correct |
| 20 |
Correct |
4 ms |
504 KB |
Output is correct |
| 21 |
Correct |
3 ms |
504 KB |
Output is correct |
| 22 |
Correct |
4 ms |
636 KB |
Output is correct |
| 23 |
Correct |
3 ms |
632 KB |
Output is correct |
| 24 |
Correct |
4 ms |
632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
4 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
4 ms |
636 KB |
Output is correct |
| 20 |
Correct |
4 ms |
504 KB |
Output is correct |
| 21 |
Correct |
3 ms |
504 KB |
Output is correct |
| 22 |
Correct |
4 ms |
636 KB |
Output is correct |
| 23 |
Correct |
3 ms |
632 KB |
Output is correct |
| 24 |
Correct |
4 ms |
632 KB |
Output is correct |
| 25 |
Correct |
21 ms |
2292 KB |
Output is correct |
| 26 |
Correct |
59 ms |
4852 KB |
Output is correct |
| 27 |
Correct |
166 ms |
11004 KB |
Output is correct |
| 28 |
Correct |
153 ms |
11244 KB |
Output is correct |
| 29 |
Correct |
116 ms |
9324 KB |
Output is correct |
| 30 |
Correct |
189 ms |
11372 KB |
Output is correct |
| 31 |
Correct |
259 ms |
18152 KB |
Output is correct |
| 32 |
Correct |
237 ms |
13796 KB |
Output is correct |
| 33 |
Correct |
33 ms |
4340 KB |
Output is correct |
| 34 |
Correct |
122 ms |
13548 KB |
Output is correct |
| 35 |
Correct |
190 ms |
26308 KB |
Output is correct |
| 36 |
Correct |
290 ms |
26480 KB |
Output is correct |
| 37 |
Correct |
232 ms |
26340 KB |
Output is correct |
| 38 |
Correct |
220 ms |
26340 KB |
Output is correct |
