#include <bits/stdc++.h>
#define int long long
#define in cin
#define out cout
using namespace std;
//ifstream in("in.in");
//ofstream out("out.out");
int n, m;
const int inf = (1LL << 60);
struct Dev {
int l, r, hole, cost;
};
vector<Dev> dev;
struct SegTree {
int l, r, val; /// val = min
SegTree *lChild, *rChild;
SegTree(int l, int r) : l(l), r(r) {
if (l == r) {
val = inf;
} else {
int mij = (l + r) / 2;
lChild = new SegTree(1, mij);
rChild = new SegTree(mij + 1, r);
recalc();
}
}
void recalc() {
val = min(lChild->val, rChild->val);
}
void update(int p, int newVal) {
if (p < l || p > r) return;
if (l == p && r == p) {
val = min(val, newVal);
return;
}
lChild->update(p, newVal);
rChild->update(p, newVal);
recalc();
}
int query(int ql, int qr) {
if (qr < l || ql > r) return inf;
if (ql <= l && r <= qr) {
return val;
}
return min(lChild->query(ql, qr), rChild->query(ql, qr));
}
};
template <typename F>
int getDp(vector<int> &dp, F f) {
/// we want to have all the pinballs take it past left
// dp[i] = minCost to get all balls to this device
dp.resize(m + 1);
for (int i = 1; i <= m; i++) {
dp[i] = inf;
}
int ans = inf;
for (int i = 1; i <= m; i++) {
if (f(dev[i])) {
dp[i] = dev[i].cost;
}
for (int j = 1; j < i; j++) {
if (dev[i].l <= dev[j].hole && dev[j].hole <= dev[i].r) {
dp[i] = min(dp[i], dp[j] + dev[i].cost);
}
}
}
return ans;
}
set<int> values;
unordered_map<int, int> valToNorm;
int32_t main() {
in >> m >> n;
/// m is number of lines, n is number of collumns
vector<pair<int, int>> sortDev;
sortDev.resize(m + 1);
dev.resize(m + 1);
for (int i = 1; i <= m; i++) {
int l, r, hole, cost;
in >> l >> r >> hole >> cost;
values.insert(l);
values.insert(r);
values.insert(hole);
dev[i] = {l, r, hole, cost};
sortDev[i] = {l, r};
}
sort(sortDev.begin(), sortDev.end());
{
int r = 1;
for (int i = 1; i <= m; i++) {
if (dev[i].l > r) {
out << "-1\n";
return 0;
}
r = max(r, dev[i].r);
}
}
int nr = 0;
for (auto k : values) {
valToNorm[k] = ++nr;
}
for (int i = 1; i <= m; i++) {
dev[i].l = valToNorm[dev[i].l];
dev[i].r = valToNorm[dev[i].r];
dev[i].hole = valToNorm[dev[i].hole];
}
n = nr;
vector<int> leftDp, rightDp;
getDp(leftDp, [&](Dev x) {
return x.l == 1;
});
getDp(rightDp, [&](Dev x) {
return x.r == n;
});
int ans = inf;
for (int i = 1; i <= m; i++) {
/// i is middle
int leftCost = inf, rightCost = inf;
if (dev[i].l > 1) {
for (int j = 1; j < i; j++) {
// if (i == j) continue;
if (dev[i].l <= dev[j].hole && dev[j].hole <= dev[i].r) {
leftCost = min(leftCost, leftDp[j]);
}
}
} else {
leftCost = 0;
}
if (dev[i].r < n) {
for (int j = 1; j < i; j++) {
// if (i == j) continue;
if (dev[i].l <= dev[j].hole && dev[j].hole <= dev[i].r) {
rightCost = min(rightCost, rightDp[j]);
}
}
} else {
rightCost = 0;
}
ans = min(ans, leftCost + rightCost + dev[i].cost);
// cout << "\n";
}
if (ans == inf) {
out << "-1\n";
} else {
out << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
