#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 = 1e5 + 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){
cout << a.first << endl;
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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
