#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 3e5 + 1;
vector <int> t(4 * nmax, -INT_MAX);
void update(int v, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r){
t[v] = max(t[v], val);
return;
}
int m= (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v +1, m + 1, r, pos, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int get(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return -INT_MAX;
if(l >= st && r <= fin)
return t[v];
int m = (l + r) / 2;
int x = get(2 * v, l, m, st, fin);
int y = get(2 * v + 1, m+ 1, r, st, fin);
return max(x, y);
}
int main(){
int n; cin >> n;
int ans[n + 1];
fill(ans, ans + n + 1, 0);
int m; cin >> m;
vector <vector <pii> > vec(n + 1);
for(int i = 1; i <= m; i++){
int l, r, x; cin >> l >> r >> x;
vec[l].pb({r, x});
}
for(int i = 1; i <= n; i++){
for(auto to : vec[i]){
int r = to.f, val = to.s;
update(1, 1, n, r, val - i);
}
int v = get(1, 1, n, i, n);
ans[i] = max(ans[i], v + i);
}
for(int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5012 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5076 KB |
Output is correct |
6 |
Correct |
10 ms |
5076 KB |
Output is correct |
7 |
Correct |
228 ms |
15684 KB |
Output is correct |
8 |
Correct |
221 ms |
17188 KB |
Output is correct |
9 |
Correct |
231 ms |
17376 KB |
Output is correct |
10 |
Correct |
247 ms |
17132 KB |
Output is correct |
11 |
Correct |
309 ms |
19112 KB |
Output is correct |
12 |
Correct |
339 ms |
19484 KB |
Output is correct |
13 |
Correct |
322 ms |
20104 KB |
Output is correct |
14 |
Correct |
290 ms |
20380 KB |
Output is correct |
15 |
Correct |
334 ms |
22224 KB |
Output is correct |
16 |
Correct |
343 ms |
22328 KB |
Output is correct |
17 |
Correct |
332 ms |
22624 KB |
Output is correct |
18 |
Correct |
391 ms |
23960 KB |
Output is correct |
19 |
Correct |
354 ms |
22912 KB |
Output is correct |
20 |
Correct |
389 ms |
26432 KB |
Output is correct |