#include <bits/stdc++.h>
#define endl '\n'
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199, inf = 1e18;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
struct segtree {
int n;
vector<ll> tree;
segtree() {}
segtree(int size) {
n = max(2, size);
while (n != (n & -n)) n += (n & -n);
tree.resize(2 * n, inf);
}
void fix(int x) {
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
}
void upd(int pos, ll x) {
pos += n - 1;
tree[pos] = min(tree[pos], x);
pos = (pos - 1) / 2;
while (pos) {
fix(pos);
pos = (pos - 1) / 2;
}
fix(0);
}
ll query(int l, int r) {
ll rtn = inf;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) rtn = min(rtn, tree[l++]);
if (r & 1) rtn = min(rtn, tree[r--]);
}
if (l == r) rtn = min(rtn, tree[l]);
return rtn;
}
ll operator [](int pos) {
return tree[pos + n - 1];
}
};
struct obj {
int l, r, p, c;
obj() {}
obj(int ll, int rr, int pp, int cc) {
l = ll;
r = rr;
p = pp;
c = cc;
}
};
int n, m;
vector<obj> a;
segtree L, R;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
a.resize(n);
map<int, int> comp;
for (int i = 0, par[4]; i < n; i++) {
cin >> par[0] >> par[1] >> par[2] >> par[3];
comp[par[0]] = comp[par[1]] = comp[par[2]] = 0;
a[i] = obj(par[0], par[1], par[2], par[3]);
}
int x = 0;
for (auto &i : comp) i.second = x++;
for (auto &i : a) {
i.l = comp[i.l];
i.r = comp[i.r];
i.p = comp[i.p];
}
m = comp.size();
L = R = segtree(n);
ll ans = inf;
for (const auto &i : a) {
if (i.r == m - 1)
R.upd(i.p, i.c);
else
R.upd(i.p, i.c + R.query(i.l, i.r));
if (i.l == 0)
L.upd(i.p, i.c);
else
L.upd(i.p, i.c + L.query(i.l, i.r));
ans = min(ans, R[i.p] + L[i.p] - i.c);
}
if (ans == inf) finish(-1);
finish(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
