#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 3e5+3;
int m, n;
const ll inf = 1LL << 60;
ll dp1[M], dp2[M], a[M], b[M], c[M], d[M];
struct SegTree{
ll t[M * 4], tag[M * 4];
void pushdown(int u, int v){
if(tag[u] != -1){
t[v] = tag[v] = tag[u];
}
}
void push(int v){
if(tag[v] != -1){
pushdown(v, v * 2);
pushdown(v, v * 2 + 1);
}
tag[v] = -1;
}
void build(ll* val, int v = 1, int tl = 0, int tr = n - 1){
if(tl == tr){
t[v] = val[tl]; tag[v] = -1;
return;
}
int tm = (tl + tr) / 2;
build(val, v * 2, tl, tm);
build(val, v * 2 + 1, tm + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
tag[v] = -1;
}
ll qry_min(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return inf;
if(l <= tl && tr <= r) return t[v];
push(v);
int tm = (tl + tr) / 2;
return min(qry_min(l, min(tm, r), v * 2, tl, tm),
qry_min(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
}
void upd(int l, int r, ll val, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return;
if(l <= tl && tr <= r){
t[v] = tag[v] = val;
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(l, min(tm, r), val, v * 2, tl, tm);
upd(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
} seg1, seg2;
int main(){
cin >> m >> n;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
{
set<int> S; for(int i = 0; i < m; i++) S.insert(a[i]), S.insert(b[i]), S.insert(c[i]);
map<int, int> M; int idx = 0; for(auto i : S) M[i] = idx++; n = idx;
for(int i = 0; i < m; i++) a[i] = M[a[i]], b[i] = M[b[i]], c[i] = M[c[i]];
}
// cout << n << endl;
// for(int i = 0; i < m; i++){
// cout << a[i] << ' ' << b[i] << ' ' << c[i] << endl;
// }
fill(dp1 + 1, dp1 + n, inf);
fill(dp2, dp2 + n - 1, inf);
seg1.build(dp1);
seg2.build(dp2);
cout << seg2.qry_min(1, n - 1) << endl;
ll ans = inf;
for(int i = 0; i < m; i++){
ans = min(ans, seg1.qry_min(a[i], n - 1) + seg2.qry_min(0, b[i]) + d[i]);
{
ll mn = seg1.qry_min(a[i], c[i]);
seg1.upd(c[i], c[i], min(seg1.qry_min(c[i], c[i]), mn + d[i]));
}
{
ll mn = seg2.qry_min(c[i], b[i]);
seg2.upd(c[i], c[i], min(seg2.qry_min(c[i], c[i]), mn + d[i]));
}
// for(int i = 0; i < n; i++){
// cout << seg1.qry_min(i, i) << ' ';
// }
// cout << endl;
// for(int i = 0; i < n; i++){
// cout << seg2.qry_min(i, i) << ' ';
// }
// cout << endl;
}
cout << (ans == inf ? -1 : ans) << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
