#include <bits/stdc++.h>
using namespace std;
const int nx=3e5+5;
#define ll long long
ll n, m, l, r, x;
struct segtree
{
ll d[4*nx];
void update(int l, int r, int i, int ql, int qr, ll x)
{
if (r<ql||qr<l) return;
if (ql<=l&&r<=qr) return void(d[i]=max(d[i], x));
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, x);
update(md+1, r, 2*i+1, ql, qr, md+1-l+x);
}
void show(int l, int r, int i)
{
if (l==r) return void(cout<<max(d[i], 0ll)<<' ');
int md=(l+r)/2;
d[2*i]=max(d[2*i], d[i]);
show(l, md, 2*i);
d[2*i+1]=max(d[2*i+1], d[i]+md);
show(md+1, r, 2*i+1);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++) s.d[i]=LLONG_MIN;
for (int i=0; i<m; i++) cin>>l>>r>>x, s.update(1, n, 1, l, r, x-l+1);
s.show(1, n, 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
