#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 1e5;
constexpr int base = (1 << 19);
int lft[LIM + 10];
int rgt[LIM + 10];
int mid[LIM + 10];
int cost[LIM + 10];
ll dp[LIM + 10][2];
ll tri[2 * base];
map<int, int>con;
void reset() {
for(int i = 0; i < 2 * base; i++) {
tri[i] = 1e18;
}
}
void upd(int v, ll x) {
v += base;
tri[v] = x;
v /= 2;
while(v > 0) {
tri[v] = min(tri[2 * v], tri[2 * v + 1]);
v /= 2;
}
}
ll que(int l, int r) {
l += base;
r += base;
ll ans = 1e18;
while(l <= r) {
if(l & 1) {
ans = min(ans, tri[l]);
}
if(!(r & 1)) {
ans = min(ans, tri[r]);
}
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> lft[i] >> rgt[i] >> mid[i] >> cost[i];
con[lft[i]] = 0;
con[rgt[i]] = 0;
con[mid[i]] = 0;
}
con[1] = 0;
con[m] = 0;
int k = 1;
for(auto x : con) {
con[x.st] = k++;
}
reset();
upd(1, 0);
for(int i = 1; i <= n; i++) {
dp[i][0] = que(con[lft[i]], con[rgt[i]]) + cost[i];
upd(con[mid[i]], dp[i][0]);
}
reset();
upd(con.size(), 0);
for(int i = 1; i <= n; i++) {
dp[i][1] = que(con[lft[i]], con[rgt[i]]) + cost[i];
upd(con[mid[i]], dp[i][1]);
}
ll ans = 1e18;
for(int i = 1; i <= n; i++) {
//cout << dp[i][0] << ' ' << dp[i][1] << '\n';
ans = min(ans, dp[i][0] + dp[i][1] - cost[i]);
}
if(ans == 1e18) {
cout << -1 << '\n';
}
else {
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
