#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
int64 a[maxn], b[maxn], c[maxn], cost[maxn];
vector <int64> coord;
int64 l[12 * maxn];// l[i] -> min cost sa ajungi in device i incepand de pe coloana 1
int64 r[12 * maxn];// r[i] -> min cost sa ajungi in device i incepand de pe coloana m
int64 query (int x, int l, int r, int il, int ir, int64 sgt[]) {
if (il <= l && r <= ir) return sgt[x];
if (l > ir || r < il) return 1e18;
int mid = (l + r) / 2;
return min(query(2 * x, l, mid, il, ir, sgt), query(2 * x + 1, mid + 1, r, il, ir, sgt));
}
int64 update (int x, int l, int r, int pos, int64 val, int64 sgt[]) {
if (l == pos && r == pos) return sgt[x] = val;
if (l > pos || r < pos) return 1e18;
int mid = (l + r) / 2;
return sgt[x] = min(update(2 * x, l, mid, pos, val, sgt), update(2 * x + 1, mid + 1, r, pos, val, sgt));
}
int main() {
int64 n,m;
cin >> n >> m;
bool f1 = 0, f2 = 0;
for (int i = 0; i < 12 * maxn; i++){
l[i] = r[i] = 1e18;
}
for (int i = 0; i < n; i++){
cin >> a[i] >> b[i] >> c[i] >> cost[i];
if (a[i] == 1) f1 = 1;
if (b[i] == m) f2 = 1;
coord.push_back(a[i]);
coord.push_back(b[i]);
coord.push_back(c[i]);
}
if (!f1 || !f2){
cout << -1;
return 0;
}
sort(coord.begin(), coord.end());
m = 0;
for (int i = 0; i < n; i++){
a[i] = lower_bound(coord.begin(), coord.end(), a[i]) - coord.begin();
b[i] = lower_bound(coord.begin(), coord.end(), b[i]) - coord.begin();
c[i] = lower_bound(coord.begin(), coord.end(), c[i]) - coord.begin();
m = max(m, b[i]);
// cout << a[i] << " " << b[i] << " " << c[i] << "\n";
}
int64 rs = 1e18;
for (int i = 0; i < n; i++){
if (a[i] == 0) update(1, 0, 3 * n, c[i], cost[i], l);
else update(1, 0, 3 * n, c[i], min(query(1, 0, 3 * n, a[i], b[i], l), query(1, 0, 3 * n, a[i], b[i], l)) + cost[i], l);
if (b[i] == m) update(1, 0, 3 * n, c[i], cost[i], r);
else update(1, 0, 3 * n, c[i], min(query(1, 0, 3 * n, a[i], b[i], r), query(1, 0, 3 * n, a[i], b[i], r)) + cost[i], r);
// cout << i << " " << query(1, 0, 3 * n, c[i], c[i], l) << " " << query(1, 0, 3 * n, c[i], c[i], r) << "\n";
rs = min(rs, query(1, 0, 3 * n, c[i], c[i], l) + query(1, 0, 3 * n, c[i], c[i], r) - cost[i]);
}
cout << (rs >= 1e15 ? -1: rs);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
