#include <bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int const mxN = 3e5+5;
int seg[8*mxN], cor[8*mxN];
int n,pw,m,b;
void update ( int node, int l_n, int r_n, int l, int r, int val , int take) {
if(r_n<=l || l_n>=r) return;
if(l<=l_n && r>=r_n) {
val = (l_n-b) + val;
seg[node] = max({seg[node],val,take});
return;
}
take = max(take, seg[node]);
int m = (l_n+r_n)/2;
update(node*2+1, l_n, m, l, r, val, take);
if(take) take += (m-l_n);
update(node*2+2, m, r_n, l, r, val, take);
}
void down ( int node, int l, int r, int v) {
seg[node] = max (seg[node], v);
if(l==r-1) { cor[l] = node; return; }
v = max(v,seg[node]);
int m = (l+r)/2;
down(node*2+1, l, m, v);
if(v) v += m-l;
down(node*2+2, m, r, v);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin>>n>>m;
pw = (1<<(__lg(n)+1));
for(int i=0; i<m; i++) {
int x,y,c; cin>>x>>y>>c;
b = x;
update(0,0,pw,x,y+1, c, 0);
}
//for(int i=0; i<=14; i++) cout<<i<<' '<<seg[i]<<'\n';
down(0,0,pw,0);
for(int i=1; i<=n; i++) {
cout<<seg[cor[i]]<<' ';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
74 ms |
7972 KB |
Output is correct |
8 |
Correct |
86 ms |
9300 KB |
Output is correct |
9 |
Correct |
94 ms |
8932 KB |
Output is correct |
10 |
Correct |
89 ms |
8020 KB |
Output is correct |
11 |
Correct |
101 ms |
10584 KB |
Output is correct |
12 |
Correct |
104 ms |
9556 KB |
Output is correct |
13 |
Correct |
106 ms |
10580 KB |
Output is correct |
14 |
Correct |
119 ms |
9816 KB |
Output is correct |
15 |
Correct |
124 ms |
11092 KB |
Output is correct |
16 |
Correct |
125 ms |
11124 KB |
Output is correct |
17 |
Correct |
133 ms |
13436 KB |
Output is correct |
18 |
Correct |
136 ms |
14420 KB |
Output is correct |
19 |
Correct |
132 ms |
13488 KB |
Output is correct |
20 |
Correct |
161 ms |
15700 KB |
Output is correct |