#include <bits/stdc++.h>
const int N = 300001;
const int64_t inf = 1e15;
struct segtree{
int64_t t[4*N];
int64_t query(int v, int tl, int tr, int l, int r) {
if(tl > r || tr < l) {
return -inf;
}
if(tl >= l && tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
return std::max(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
}
void update(int v, int tl, int tr, int index, int64_t value) {
if(tl == tr) {
t[v] = std::max(t[v], value);
}
else {
int tm = (tl + tr) / 2;
if(index <= tm) {
update(v * 2, tl, tm, index, value);
}
else {
update(v * 2 + 1, tm + 1, tr, index, value);
}
t[v] = std::max(t[v * 2], t[v * 2 + 1]);
}
}
}seg;
void solve() {
int n, m;
std::cin >> n >> m;
for(int i = 1; i <= 4 * n; i++) {
seg.t[i] = -inf;
}
std::vector<int> l(n + 1), r(n + 1), x(n + 1);
std::vector<std::pair<int,int64_t>> upd[n + 1];
for(int i = 1; i <= m; i++) {
std::cin >> l[i] >> r[i] >> x[i];
upd[l[i]].push_back({r[i], x[i] - l[i]});
}
std::vector<int64_t> ans(n + 1, 0);
for(int i = 1; i <= n; i++) {
for(auto [R, val] : upd[i]) {
seg.update(1, 1, n, R, val);
}
ans[i] = std::max(ans[i], i + seg.query(1, 1, n, i, n));
}
for(int i = 1; i <= n; i++) {
std::cout << ans[i] << " ";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |