#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e5 + 10;
int n, m, a[N], b[N], c[N], d[N];
ll fl[N], fr[N], t[N * 12];
void update(int node, int l, int r, int i, ll v) {
if(l == r) {
t[node] = v;
return;
} int m = l + r >> 1;
if(i <= m) update(node << 1, l, m, i, v);
else update(node << 1 | 1, m + 1, r, i, v);
t[node] = min(t[node << 1], t[node << 1 | 1]);
}
ll query(int node, int l, int r, int i, int j) {
if(r < i || l > j) return 1e15;
if(i <= l && r <= j) return t[node];
int m = l + r >> 1;
return min(query(node << 1, l, m, i, j),
query(node << 1 | 1, m + 1, r, i, j));
}
int main(int argc, char const *argv[]) {
scanf("%d %d", &m, &n);
vector<int> v;
for(int i = 1; i <= m; i++) {
scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
v.push_back(a[i]);
v.push_back(b[i]);
v.push_back(c[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
map<int, int> mp, rev;
for(int i = 0; i < v.size(); i++) {
mp[v[i]] = i + 1;
rev[i + 1] = v[i];
}
for(int i = 1; i <= m; i++) {
a[i] = mp[a[i]];
b[i] = mp[b[i]];
c[i] = mp[c[i]];
}
int L = mp.size() + 1;
for(int i = 0; i < 4 * L; i++) t[i] = 1e15;
for(int i = 1; i <= m; i++) {
if(rev[a[i]] == 1) fl[i] = d[i];
else fl[i] = query(1, 1, L, a[i], b[i]) + d[i];
update(1, 1, L, c[i], fl[i]);
}
for(int i = 0; i < 4 * L; i++) t[i] = 1e15;
for(int i = 1; i <= m; i++) {
if(rev[b[i]] == n) fr[i] = d[i];
else fr[i] = query(1, 1, L, a[i], b[i]) + d[i];
update(1, 1, L, c[i], fr[i]);
}
ll ans = 1e18;
for(int i = 1; i <= m; i++) {
ans = min(ans, fl[i] + fr[i] - d[i]);
}
if(ans > 1e15) ans = -1;
printf("%lld\n", ans);
}
Compilation message
pinball.cpp: In function 'void update(int, int, int, int, ll)':
pinball.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
} int m = l + r >> 1;
~~^~~
pinball.cpp: In function 'll query(int, int, int, int, int)':
pinball.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
pinball.cpp: In function 'int main(int, const char**)':
pinball.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
pinball.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &m, &n);
~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
