# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int t,n,a[N],m,le,ri,x;
int lazy[4*N],tree[4*N];
void update(int node,int le,int ri,int start,int end,int val) {
if(lazy[node]) {
tree[node] = max(tree[node], lazy[node]);
if(le!=ri) {
lazy[2*node] = max(lazy[2*node],lazy[node]);
lazy[2*node+1] = max(lazy[2*node + 1], lazy[node]);
}
lazy[node]=0;
}
if(le>end || ri<start)
return;
if(start<=le && ri<=end) {
tree[node] = max(tree[node],val);
if(le != ri) {
lazy[2*node] = max(lazy[2*node],val);
lazy[2*node+1] = max(lazy[2*node + 1], val);
}
return;
}
int mid=(le+ri)/2;
update(2*node,le,mid,start,end,val);
update(2*node+1,mid+1,ri,start,end,val);
tree[node]=max(tree[2*node],tree[2*node+1]);
}
int getans(int node,int le,int ri,int start,int end) {
if(lazy[node]) {
tree[node] = max(tree[node], lazy[node]);
if(le!=ri) {
lazy[2*node] = max(lazy[2*node],lazy[node]);
lazy[2*node+1] = max(lazy[2*node + 1], lazy[node]);
}
lazy[node]=0;
}
if(le>end || ri<start) return -1e9;
if(start<=le && ri<=end) {
return tree[node];
}
int mid=(le+ri)/2;
return max(getans(2*node,le,mid,start,end), getans(2*node+1,mid+1,ri,start,end));
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (int i = 1; i <= m; i++) {
cin>>le>>ri>>x;
update(1,1,n,le,ri,x-le+300000);
}
for (int i = 1; i <= n; i++) {
cout<<max(0, getans(1,1,n,i,i) + i - 300000)<<" ";
}
}
Compilation message
trading.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
456 KB |
Output is correct |
7 |
Correct |
138 ms |
6728 KB |
Output is correct |
8 |
Correct |
169 ms |
8260 KB |
Output is correct |
9 |
Correct |
176 ms |
7428 KB |
Output is correct |
10 |
Correct |
179 ms |
6088 KB |
Output is correct |
11 |
Correct |
184 ms |
9092 KB |
Output is correct |
12 |
Correct |
195 ms |
7796 KB |
Output is correct |
13 |
Correct |
211 ms |
8756 KB |
Output is correct |
14 |
Correct |
213 ms |
7576 KB |
Output is correct |
15 |
Correct |
242 ms |
9036 KB |
Output is correct |
16 |
Correct |
253 ms |
8900 KB |
Output is correct |
17 |
Correct |
248 ms |
11300 KB |
Output is correct |
18 |
Correct |
260 ms |
12640 KB |
Output is correct |
19 |
Correct |
262 ms |
11008 KB |
Output is correct |
20 |
Correct |
295 ms |
13304 KB |
Output is correct |