#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e5+5;
int val_ind[N],l[N*4],r[N*4];
void build(int v,int tl,int tr){
if(tl==tr){
l[v]=1e16;
r[v]=1e16;
}
else{
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
l[v]=min(l[v*2],l[v*2+1]);
r[v]=min(r[v*2],r[v*2+1]);
}
}
int get_min_l(int v,int tl,int tr,int L,int R){
if(tr<L or R<tl)return 1e18;
if(L<=tl && tr<=R)return l[v];
int tm=(tl+tr)/2;
return min(get_min_l(v*2,tl,tm,L,R), get_min_l(v*2+1,tm+1,tr,L,R));
}
int get_min_r(int v,int tl,int tr,int L,int R){
if(tr<L or R<tl)return 1e18;
if(L<=tl && tr<=R)return r[v];
int tm=(tl+tr)/2;
return min(get_min_r(v*2,tl,tm,L,R), get_min_r(v*2+1,tm+1,tr,L,R));
}
void update_l(int v,int tl,int tr,int pos,int val){
if(tl==tr)l[v]=min(val,l[v]);
else{
int tm=(tl+tr)/2;
if(pos<=tm)update_l(v*2,tl,tm,pos,val);
else update_l(v*2+1,tm+1,tr,pos,val);
l[v]=min(l[v*2],l[v*2+1]);
}
}
void update_r(int v,int tl,int tr,int pos,int val){
if(tl==tr)r[v]=min(val,r[v]);
else{
int tm=(tl+tr)/2;
if(pos<=tm)update_r(v*2,tl,tm,pos,val);
else update_r(v*2+1,tm+1,tr,pos,val);
r[v]=min(r[v*2],r[v*2+1]);
}
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);
int m,n;
cin>>m>>n;
vector <int> a(m),b(m),c(m),d(m);
set <int> st;
st.insert(1);st.insert(n);
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
st.insert(a[i]);
st.insert(b[i]);
st.insert(c[i]);
}
int cnt=1;
for(auto x : st){
val_ind[x]=cnt;
cnt++;
}
n=st.size();
build(1,1,n);
int ans=1e16;
for(int i=0;i<m;i++){
int res=0;
if(a[i]==1){
res+=d[i];
update_l(1,1,n,val_ind[c[i]],d[i]);
}
else{
int x=get_min_l(1,1,n,val_ind[a[i]],val_ind[b[i]]);
res+=x;res+=d[i];
update_l(1,1,n,val_ind[c[i]],x+d[i]);
}
if(b[i]==n){
res+=d[i];
update_r(1,1,n,val_ind[c[i]],d[i]);
}
else{
int x=get_min_r(1,1,n,val_ind[a[i]],val_ind[b[i]]);
res+=x;res+=d[i];
update_r(1,1,n,val_ind[c[i]],x+d[i]);
}
ans=min(ans,res-d[i]);
}
if(ans==1e16)ans=-1;
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
