#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int, int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a != b) cerr << *a << " \n"[(a = next(a)) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif
struct Lisan: vector<int> {
void done() { sort(AI()); erase(unique(AI()), end()); }
int operator () (const int& v) const { return std::lower_bound(AI(), v) - begin(); }
int upper_bound (const int& v) const { return std::upper_bound(AI(), v) - begin(); }
};
struct SGT {
int n; vector<ll> val;
SGT (int _n): n(_n), val(n * 4, INT_MAX) { }
ll query(int i, int l, int r, int ql, int qr) {
if (ql <= l and r <= qr) return val[i];
int m = (l + r) / 2;
ll ans = INT_MAX;
if (ql < m) ans = min(ans, query(i * 2, l, m, ql, qr));
if (m < qr) ans = min(ans, query(i*2+1, m, r, ql, qr));
return ans;
}
void modify(int i, int l, int r, int p, ll v) {
if (l + 1 == r) {
val[i] = min(val[i], v);
return;
}
int m = (l + r) / 2;
if (p < m) modify(i * 2, l, m, p, v);
else modify(i * 2 + 1, m, r, p, v);
val[i] = min(val[i * 2], val[i * 2 + 1]);
}
ll query(int ql, int qr) { return query(1, 0, n, ql, qr); }
void modify(int p, ll v) { modify(1, 0, n, p, v); }
};
void gg() {
cout << -1 << '\n';
exit(0);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M;
cin >> N >> M;
vector<tuple<int, int, int>> ts;
Lisan lisan;
ts.reserve(M);
lisan.reserve(M + 1);
lisan.pb(1);
for (int T, L, R, C, i = 0; i < M; ++i) {
cin >> T >> L >> R >> C;
assert(T == 1);
ts.pb(L, R, C);
lisan.pb(R + 1);
}
sort(AI(ts));
lisan.done();
SGT sgt(lisan.size());
sgt.modify(0, 0);
for (auto& [l, r, c]: ts) {
l = lisan(l);
r = lisan.upper_bound(r);
ll v = sgt.query(l, r);
debug(l, r, c, v);
sgt.modify(r, v + c);
}
if (lisan.back() != N + 1) gg();
int pos = lisan.size() - 1;
ll ans = sgt.query(pos, pos + 1);
cout << ans << '\n';
return 0;
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
treatment.cpp:82:3: note: in expansion of macro 'debug'
82 | debug(l, r, c, v);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
4900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
4900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
