#include <bits/stdc++.h>
#define MAXN 100007
#define LINF 1000000000000000000LL
using namespace std;
long long dpl[MAXN],dpr[MAXN],seg[2][12*MAXN],d[MAXN];
int a[MAXN],b[MAXN],c[MAXN],sz;
vector<int> v;
map<int,int> mp;
void upd(int k,int l,int r,int v,long long a,int ind)
{
if(l==r) {seg[k][ind]=min(seg[k][ind],a); return;}
int s=(l+r)/2;
if(v<=s) upd(k,l,s,v,a,2*ind);
else upd(k,s+1,r,v,a,2*ind+1);
seg[k][ind]=fmin(seg[k][2*ind],seg[k][2*ind+1]);
}
long long val(int k,int l,int r,int lt,int rt,int ind)
{
if(l>=lt && r<=rt) return seg[k][ind];
if(rt<l || lt>r) return LINF;
int s=(l+r)/2;
return min(val(k,l,s,lt,rt,2*ind),val(k,s+1,r,lt,rt,2*ind+1));
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n,m; cin>>m>>n;
v.push_back(1);
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(n);
sort(v.begin(),v.end());
sz=v.size();
for(int i=0;i<sz;i++) mp[v[i]]=i;
fill(seg[1],seg[1]+12*MAXN,LINF); fill(seg[0],seg[0]+12*MAXN,LINF);
upd(0,0,4*sz,mp[1],0,1); upd(1,0,4*sz,mp[n],0,1);
long long sol=LINF;
for(int i=0;i<m;i++)
{
long long x=val(0,0,4*sz,mp[a[i]],mp[b[i]],1),y=val(1,0,4*sz,mp[a[i]],mp[b[i]],1);
//cout<<mp[a[i]]<<" "<<y<<endl;
upd(0,0,4*sz,mp[c[i]],x+d[i],1); upd(1,0,4*sz,mp[c[i]],y+d[i],1);
sol=min(sol,x+y+d[i]);
}
if(sol==LINF) sol=-1;
cout<<sol;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
21 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
20 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
17 ms |
19200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
21 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
20 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 9 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 10 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 11 |
Correct |
18 ms |
19172 KB |
Output is correct |
| 12 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 13 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 14 |
Correct |
17 ms |
19200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
21 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
20 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 9 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 10 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 11 |
Correct |
18 ms |
19172 KB |
Output is correct |
| 12 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 13 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 14 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 15 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 16 |
Correct |
20 ms |
19136 KB |
Output is correct |
| 17 |
Correct |
22 ms |
19300 KB |
Output is correct |
| 18 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 19 |
Correct |
19 ms |
19468 KB |
Output is correct |
| 20 |
Correct |
22 ms |
19200 KB |
Output is correct |
| 21 |
Correct |
18 ms |
19212 KB |
Output is correct |
| 22 |
Correct |
21 ms |
19328 KB |
Output is correct |
| 23 |
Correct |
25 ms |
19328 KB |
Output is correct |
| 24 |
Correct |
19 ms |
19328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
21 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 7 |
Correct |
20 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 9 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 10 |
Correct |
18 ms |
19200 KB |
Output is correct |
| 11 |
Correct |
18 ms |
19172 KB |
Output is correct |
| 12 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 13 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 14 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 15 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 16 |
Correct |
20 ms |
19136 KB |
Output is correct |
| 17 |
Correct |
22 ms |
19300 KB |
Output is correct |
| 18 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 19 |
Correct |
19 ms |
19468 KB |
Output is correct |
| 20 |
Correct |
22 ms |
19200 KB |
Output is correct |
| 21 |
Correct |
18 ms |
19212 KB |
Output is correct |
| 22 |
Correct |
21 ms |
19328 KB |
Output is correct |
| 23 |
Correct |
25 ms |
19328 KB |
Output is correct |
| 24 |
Correct |
19 ms |
19328 KB |
Output is correct |
| 25 |
Correct |
59 ms |
20708 KB |
Output is correct |
| 26 |
Correct |
153 ms |
23408 KB |
Output is correct |
| 27 |
Incorrect |
475 ms |
27792 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
