#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int m,n,a[nmax],b[nmax],c[nmax],d[nmax],sz,i;
ll f[nmax],g[nmax],x,st[12*nmax],rs;
vector<int>vc;
void upd(int nod,int l,int r,int p,ll v)
{
if(l==r)
{
st[nod]=min(st[nod],v);
return;
}
int mid=(l+r)/2;
if(p<=mid)upd(2*nod,l,mid,p,v);
else upd(2*nod+1,mid+1,r,p,v);
st[nod]=min(st[2*nod],st[2*nod+1]);
}
ll qry(int nod,int l,int r,int tl,int tr)
{
if(tr<l || tl>r)return llinf;
if(tl<=l && r<=tr)return st[nod];
int mid=(l+r)/2;
return min(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>m>>n;
for(i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>c[i]>>d[i];
vc.pb(a[i]);
vc.pb(b[i]);
vc.pb(c[i]);
}
vc.pb(1),vc.pb(n);
sort(all(vc));
vc.resize(unique(all(vc))-vc.begin());
sz=lun(vc);
for(i=1;i<=m;i++)
{
a[i]=lower_bound(all(vc),a[i])-vc.begin()+1;
b[i]=lower_bound(all(vc),b[i])-vc.begin()+1;
c[i]=lower_bound(all(vc),c[i])-vc.begin()+1;
}
for(i=1;i<=sz;i++)upd(1,1,sz,i,llinf);
for(i=1;i<=m;i++)
{
f[i]=llinf;
x=qry(1,1,sz,a[i],b[i]);
if(a[i]==1)f[i]=d[i];
else if(x!=llinf)f[i]=x+d[i];
upd(1,1,sz,c[i],f[i]);
}
for(i=1;i<=sz;i++)upd(1,1,sz,i,llinf);
rs=llinf;
for(i=1;i<=m;i++)
{
g[i]=llinf;
x=qry(1,1,sz,a[i],b[i]);
if(b[i]==sz)g[i]=d[i];
else if(x!=llinf)g[i]=x+d[i];
upd(1,1,sz,c[i],g[i]);
if(f[i]!=llinf && g[i]!=llinf)rs=min(rs,f[i]+g[i]-d[i]);
}
if(rs==llinf)rs=-1;
cout<<rs<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
