#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int N = 3e5 + 5;
int n, m;
int a[N], b[N], c[N], d[N];
vector<int> num;
ll st[2][N << 2];
void update(int u, ll val, int t) {
int id = 1, l = 1, r = n;
while(l < r) {
int mid = l + r >> 1;
if(u > mid) id = id << 1 | 1, l = mid + 1;
else id = id << 1, r = mid;
}
st[t][id] = min(st[t][id], val);
while(id > 1) id = id >> 1, st[t][id] = min(st[t][id << 1], st[t][id << 1 | 1]);
}
ll get(int u, int v, int t, int id = 1, int l = 1, int r = n) {
if(u > r || v < l) return 1e18;
if(u <= l && r <= v) return st[t][id];
int mid = l + r >> 1;
ll tmp1 = get(u, v, t, id << 1, l, mid);
ll tmp2 = get(u, v, t, id << 1 | 1, mid + 1, r);
return min(tmp1, tmp2);
}
void solve() {
cin >> m >> n;
num.push_back(1);
num.push_back(n);
for(int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
num.push_back(a[i]);
num.push_back(b[i]);
num.push_back(c[i]);
}
sort(all(num));
num.resize(unique(all(num)) - num.begin());
n = lower_bound(all(num), n) - num.begin() + 1;
ll ans = 1e18;
memset(st, 0x3f, sizeof(st));
for(int i = 1; i <= m; ++i) {
a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
b[i] = lower_bound(all(num), b[i]) - num.begin() + 1;
c[i] = lower_bound(all(num), c[i]) - num.begin() + 1;
ll lcost = 0, rcost = 0;
if(a[i] != 1) lcost = get(a[i], b[i], 0);
if(b[i] != n) rcost = get(a[i], b[i], 1);
cout << lcost << ' ' << rcost << '\n';
ans = min(ans, lcost + rcost + d[i]);
update(c[i], lcost + d[i], 0);
update(c[i], rcost + d[i], 1);
}
cout << (ans == 1e18 ? -1 : ans) << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) solve();
return 0;
}
Compilation message
pinball.cpp: In function 'void update(int, long long int, int)':
pinball.cpp:15:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
15 | int mid = l + r >> 1;
| ~~^~~
pinball.cpp: In function 'long long int get(int, int, int, int, int, int)':
pinball.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
