#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const ll inf = 1e18;
struct segtree {
ll t[2*N];
int n;
segtree(int n): n(n) {
for(int i = 1;i < 2*N; ++i)t[i] = inf;
}
void edit(int x, ll v){
x+=n;
gmin(t[x], v);
while(x>1){
x/=2;
t[x] = min(t[2*x],t[2*x+1]);
}
}
ll query(int l, int r){
ll res = inf;
for(l+=n,r+=n;l < r; l/=2,r/=2){
if(l&1)gmin(res,t[l++]);
if(r&1)gmin(res,t[--r]);
}
return res;
}
};
struct interval{
int l,c,r,cst;
};
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int m,n;
cin >> m >> n;
map<ll,int> comp;
comp[1] = 0;
comp[n] = 0;
vector<interval> v(m);
for(int i = 0;i < m; ++i){
cin >> v[i].l >> v[i].r >> v[i].c >> v[i].cst;
comp[v[i].l] = 0;
comp[v[i].c] = 0;
comp[v[i].r] = 0;
}
int cnt = 0;
for(auto &a: comp){
a.second = cnt++;
}
for(int i = 0;i < m; ++i){
v[i].l = comp[v[i].l];
v[i].c = comp[v[i].c];
v[i].r = comp[v[i].r];
}
segtree left(cnt), right(cnt);
left.edit(0,0);
right.edit(cnt-1,0);
ll ans = inf;
for(auto r: v){
ll bestl = left.query(r.l,r.r+1);
ll bestr = right.query(r.l,r.r+1);
gmin(ans, bestl + bestr + r.cst);
left.edit(r.c,bestl + r.cst);
right.edit(r.c,bestr + r.cst);
}
if(ans == inf)ans = -1;
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9720 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 12 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9848 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 12 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 16 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 18 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 20 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 21 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 22 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 23 |
Correct |
11 ms |
10032 KB |
Output is correct |
| 24 |
Correct |
15 ms |
9976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 12 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 13 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 16 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 18 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 20 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 21 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 22 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 23 |
Correct |
11 ms |
10032 KB |
Output is correct |
| 24 |
Correct |
15 ms |
9976 KB |
Output is correct |
| 25 |
Correct |
36 ms |
11256 KB |
Output is correct |
| 26 |
Correct |
93 ms |
14584 KB |
Output is correct |
| 27 |
Correct |
395 ms |
19792 KB |
Output is correct |
| 28 |
Correct |
144 ms |
15336 KB |
Output is correct |
| 29 |
Correct |
212 ms |
18168 KB |
Output is correct |
| 30 |
Correct |
234 ms |
16296 KB |
Output is correct |
| 31 |
Correct |
516 ms |
25860 KB |
Output is correct |
| 32 |
Correct |
445 ms |
22776 KB |
Output is correct |
| 33 |
Correct |
56 ms |
14456 KB |
Output is correct |
| 34 |
Correct |
254 ms |
21880 KB |
Output is correct |
| 35 |
Correct |
264 ms |
33988 KB |
Output is correct |
| 36 |
Correct |
673 ms |
34100 KB |
Output is correct |
| 37 |
Correct |
533 ms |
34040 KB |
Output is correct |
| 38 |
Correct |
483 ms |
34012 KB |
Output is correct |
