#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll INF = 1e18;
int rows, cols;
struct kek {
ll l;
ll r;
ll c;
ll d;
};
kek a[N];
ll aib1[3 * N], aib2[3 * N];
ll dp1[N], dp2[N];
void update1(int i, ll val) {
for (; i < 3 * N; i += i & -i) aib1[i] = min(aib1[i], val);
}
void update2(int i, ll val) {
for (; i >= 1; i -= i & -i) aib2[i] = min(aib2[i], val);
}
ll query1(int i) {
ll ans = INF;
for (; i >= 1; i -= i & -i) ans = min(ans, aib1[i]);
return ans;
}
ll query2(int i) {
ll ans = INF;
for (; i < 3 * N; i += i & -i) ans = min(ans, aib2[i]);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> rows >> cols;
for (int i = 1; i <= rows; ++i) cin >> a[i].l >> a[i].r >> a[i].c >> a[i].d;
{
vector<vector<int>> vals;
for (int i = 1; i <= rows; ++i) {
vals.push_back({a[i].l, 0, i});
vals.push_back({a[i].r, 1, i});
vals.push_back({a[i].c, 2, i});
}
sort(vals.begin(), vals.end());
//cout << "DEBUG: " << "\n";
//for (auto it : vals) {
//cout << it[0] << " " << it[1] << " " << it[2] << "\n";
//}
int cnt = 1;
for (int i = 0; i < vals.size(); ++i) {
if (i > 0 && vals[i][0] != vals[i - 1][0]) ++cnt;
auto it = vals[i];
if (it[1] == 0) a[it[2]].l = cnt;
if (it[1] == 1) a[it[2]].r = cnt;
if (it[1] == 2) a[it[2]].c = cnt;
}
}
//cout << "DEBUG: " << "\n";
//for (int i = 1; i <= rows; ++i) {
//cout << a[i].l << " " << a[i].r << " " << a[i].c << "\n";
//}
ll mx = 0;
for (int i = 1; i <= rows; ++i) {
mx = max(mx, a[i].l);
mx = max(mx, a[i].r);
mx = max(mx, a[i].c);
dp1[i] = INF;
dp2[i] = INF;
}
for (int i = 1; i < 3 * N; ++i) {
aib1[i] = INF;
aib2[i] = INF;
}
for (int i = 1; i <= rows; ++i) {
if (a[i].l == 1) dp1[i] = a[i].d;
if (a[i].r == mx) dp2[i] = a[i].d;
}
//for (int i = 1; i <= rows; ++i) cout << dp1[i] << " " << dp2[i] << "\n";
//cout << "-------\n";
ll ans = INF;
for (int i = 1; i <= rows; ++i) {
//if (i == 3) {
//cout << query2(a[i].l) << "\n";
//}
dp1[i] = min(dp1[i], query2(a[i].l) + a[i].d);
dp2[i] = min(dp2[i], query1(a[i].r) + a[i].d);
//cout << "UPDATAM " << a[i].c << " " << dp1[i] << "\n";
update2(a[i].c, dp1[i]);
update1(a[i].c, dp2[i]);
ans = min(ans, dp1[i] + dp2[i] - a[i].d);
//cout << dp1[i] << " " << dp2[i] << "\n";
}
if (ans == INF) ans = -1;
cout << ans << endl;
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:49:34: warning: narrowing conversion of 'a[i].kek::l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
49 | vals.push_back({a[i].l, 0, i});
| ~~~~~^
pinball.cpp:49:34: warning: narrowing conversion of 'a[i].kek::l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:50:34: warning: narrowing conversion of 'a[i].kek::r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
50 | vals.push_back({a[i].r, 1, i});
| ~~~~~^
pinball.cpp:50:34: warning: narrowing conversion of 'a[i].kek::r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:51:34: warning: narrowing conversion of 'a[i].kek::c' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
51 | vals.push_back({a[i].c, 2, i});
| ~~~~~^
pinball.cpp:51:34: warning: narrowing conversion of 'a[i].kek::c' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
pinball.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < vals.size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
