#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
#define in cin
#define out cout
int n, m;
const ll inf = (1LL << 60);
struct Dev {
int l, r, hole, cost;
};
vector<Dev> dev;
struct SegTree {
int l, r;
ll 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, ll 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();
}
ll 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>
void getDp(vector<ll> &dp, F f) {
SegTree segTree(1, n);
/// 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;
}
ll ans = inf;
for (int i = 1; i <= m; i++) {
if (f(dev[i])) {
dp[i] = dev[i].cost;
}
dp[i] = min(dp[i], dev[i].cost + segTree.query(dev[i].l, dev[i].r));
segTree.update(dev[i].hole, dp[i]);
}
}
set<int> values;
map<int, int> valToNorm;
int 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 (sortDev[i].first > r) {
out << "-1\n";
return 0;
}
r = max(r, sortDev[i].second);
}
if (r < n) {
out << "-1\n";
return 0;
}
}
sortDev.clear();
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];
}
valToNorm.clear();
values.clear();
n = nr;
vector<ll> leftDp, rightDp;
getDp(leftDp, [&](Dev x) {
return x.l == 1;
});
getDp(rightDp, [&](Dev x) {
return x.r == n;
});
SegTree segTreeLeft(1, n), segTreeRight(1, n);
ll ans = inf;
for (int i = 1; i <= m; i++) {
/// i is middle
ll leftCost = inf, rightCost = inf;
if (dev[i].l > 1) {
leftCost = segTreeLeft.query(dev[i].l, dev[i].r);
} else {
leftCost = 0;
}
if (dev[i].r < n) {
rightCost = segTreeRight.query(dev[i].l, dev[i].r);
} else {
rightCost = 0;
}
segTreeLeft.update(dev[i].hole, leftDp[i]);
segTreeRight.update(dev[i].hole, rightDp[i]);
ans = min(ans, leftCost + rightCost + dev[i].cost);
// cout << "\n";
}
if (ans == inf) {
out << "-1\n";
} else {
out << ans << "\n";
}
}
Compilation message
cc1plus: error: '::main' must return 'int'
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:136:6: required from here
pinball.cpp:68:8: warning: unused variable 'ans' [-Wunused-variable]
68 | ll ans = inf;
| ^~~
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:140:6: required from here
pinball.cpp:68:8: warning: unused variable 'ans' [-Wunused-variable]
