#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 22;
const ll MAXN = 1e5 + 100;
vector<int> cc;
struct Machine {
int l, r, centr;
ll cost;
void read() {
cin >> l >> r >> centr >> cost;
cc.push_back(l);
cc.push_back(r);
cc.push_back(centr);
}
Machine(int _l, int _r, int _centr, ll _cost) : l(_l), r(_r), centr(_centr), cost(_cost) { }
Machine() { }
};
vector<Machine> v;
int n;
ll sg[4*MAXN], to_right[MAXN], to_left[MAXN];
void init(int k, int a, int b) {
if (a == b) {
sg[k] = 1e16;
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = min(sg[2*k], sg[2*k+1]);
}
void update(int k, int a, int b, int plc, ll val) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k] = min(sg[k], val);
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = min(sg[2*k], sg[2*k+1]);
}
ll query(int k, int a, int b, int q_l, int q_r) {
if (q_l > b || q_r < a)
return 1e16;
if (q_l <= a && b <= q_r)
return sg[k];
return min(query(2*k, a, (a+b)/2, q_l, q_r),
query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}
int main() {
int M, N;
cin >> M >> N;
v = vector<Machine>(M+1);
for (int i = 1; i <= M; i++)
v[i].read();
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
n = cc.size();
init(1, 1, n);
for (int i = 1; i <= M; i++) {
ll Q = query(1, 1, n, v[i].l, v[i].r);
if (v[i].l == 1)
Q = 0;
to_left[i] = Q + v[i].cost;
update(1, 1, n, v[i].centr, to_left[i]);
}
init(1, 1, n);
for (int i = 1; i <= M; i++) {
ll Q = query(1, 1, n, v[i].l, v[i].r);
if (v[i].r == N)
Q = 0;
to_right[i] = Q + v[i].cost;
update(1, 1, n, v[i].centr, to_right[i]);
}
ll mn = 1e16;
for (int i = 1; i <= M; i++)
mn = min(mn, to_left[i] + to_right[i] - v[i].cost);
if (mn >= 1e14)
mn = -1;
cout << mn << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
