#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll N, M, sz;
pair<ll, pair<pii, ll>> arr[100005];
ll dp[200505];
ll seg[200505 * 2];
void update(int pos, ll v) {
pos += sz;
seg[pos] = min(seg[pos], v);
for (; pos > 0; pos >>= 1) seg[pos >> 1] = min(seg[pos], seg[pos ^ 1]);
return;
}
ll query(int l, int r) {
r++;
ll ret = inf;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret = min(ret, seg[l++]);
if (r & 1) ret = min(ret, seg[--r]);
}
return ret;
}
void solve() {
cin >> N >> M;
vector<ll> v;
v.push_back(0);
v.push_back(1), v.push_back(N);
for (int i = 0; i < M; i++) {
ll T, L, R, C;
cin >> T >> L >> R >> C;
v.push_back(L), v.push_back(R);
arr[i] = {T, {{L, R}, C}};
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
sz = v.size();
sort(arr, arr + M, [&](pair<ll, pair<pii, ll>> a, pair<ll, pair<pii, ll>> b) {
return a.second.first.second < b.second.first.second;
});
for (int i = 0; i < M; i++) {
ll L = arr[i].second.first.first, R = arr[i].second.first.second;
L = lower_bound(v.begin(), v.end(), L) - v.begin();
R = lower_bound(v.begin(), v.end(), R) - v.begin();
arr[i].second.first = {L, R};
}
memset(dp, 0x3f, sizeof(dp));
memset(seg, 0x3f, sizeof(seg));
dp[0] = 0;
update(0, dp[0]);
for (int i = 0; i < M; i++) {
ll l = arr[i].second.first.first, r = arr[i].second.first.second, c = arr[i].second.second;
ll idx = lower_bound(v.begin(), v.end(), v[l] - 1) - v.begin();
dp[r] = min(dp[r], query(idx, r) + c);
update(r, dp[r]);
}
int idx = lower_bound(v.begin(), v.end(), N) - v.begin();
if (dp[idx] == inf) cout << -1;
else cout << dp[idx];
return;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
