#include <bits/stdc++.h>
#define ll long long
#define in cin
#define out cout
using namespace std;
ifstream in("in.in");
ofstream out("out.out");
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;
unordered_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
pinball.cpp: In function 'int main()':
pinball.cpp:3:12: error: reference to 'cin' is ambiguous
3 | #define in cin
| ^~~
pinball.cpp:81:5: note: in expansion of macro 'in'
81 | in >> m >> n;
| ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:60:18: note: candidates are: 'std::istream std::cin'
60 | extern istream cin; /// Linked to standard input
| ^~~
pinball.cpp:3:12: note: 'std::ifstream cin'
3 | #define in cin
| ^~~
pinball.cpp:7:10: note: in expansion of macro 'in'
7 | ifstream in("in.in");
| ^~
pinball.cpp:3:12: error: reference to 'cin' is ambiguous
3 | #define in cin
| ^~~
pinball.cpp:89:9: note: in expansion of macro 'in'
89 | in >> l >> r >> hole >> cost;
| ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:60:18: note: candidates are: 'std::istream std::cin'
60 | extern istream cin; /// Linked to standard input
| ^~~
pinball.cpp:3:12: note: 'std::ifstream cin'
3 | #define in cin
| ^~~
pinball.cpp:7:10: note: in expansion of macro 'in'
7 | ifstream in("in.in");
| ^~
pinball.cpp:4:13: error: reference to 'cout' is ambiguous
4 | #define out cout
| ^~~~
pinball.cpp:104:17: note: in expansion of macro 'out'
104 | out << "-1\n";
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:61:18: note: candidates are: 'std::ostream std::cout'
61 | extern ostream cout; /// Linked to standard output
| ^~~~
pinball.cpp:4:13: note: 'std::ofstream cout'
4 | #define out cout
| ^~~~
pinball.cpp:8:10: note: in expansion of macro 'out'
8 | ofstream out("out.out");
| ^~~
pinball.cpp:4:13: error: reference to 'cout' is ambiguous
4 | #define out cout
| ^~~~
pinball.cpp:111:13: note: in expansion of macro 'out'
111 | out << "-1\n";
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:61:18: note: candidates are: 'std::ostream std::cout'
61 | extern ostream cout; /// Linked to standard output
| ^~~~
pinball.cpp:4:13: note: 'std::ofstream cout'
4 | #define out cout
| ^~~~
pinball.cpp:8:10: note: in expansion of macro 'out'
8 | ofstream out("out.out");
| ^~~
pinball.cpp:4:13: error: reference to 'cout' is ambiguous
4 | #define out cout
| ^~~~
pinball.cpp:168:9: note: in expansion of macro 'out'
168 | out << "-1\n";
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:61:18: note: candidates are: 'std::ostream std::cout'
61 | extern ostream cout; /// Linked to standard output
| ^~~~
pinball.cpp:4:13: note: 'std::ofstream cout'
4 | #define out cout
| ^~~~
pinball.cpp:8:10: note: in expansion of macro 'out'
8 | ofstream out("out.out");
| ^~~
pinball.cpp:4:13: error: reference to 'cout' is ambiguous
4 | #define out cout
| ^~~~
pinball.cpp:170:9: note: in expansion of macro 'out'
170 | out << ans << "\n";
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
from pinball.cpp:1:
/usr/include/c++/10/iostream:61:18: note: candidates are: 'std::ostream std::cout'
61 | extern ostream cout; /// Linked to standard output
| ^~~~
pinball.cpp:4:13: note: 'std::ofstream cout'
4 | #define out cout
| ^~~~
pinball.cpp:8:10: note: in expansion of macro 'out'
8 | ofstream out("out.out");
| ^~~
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:137:6: required from here
pinball.cpp:69:8: warning: unused variable 'ans' [-Wunused-variable]
69 | ll ans = inf;
| ^~~
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:141:6: required from here
pinball.cpp:69:8: warning: unused variable 'ans' [-Wunused-variable]
