#include <stdio.h>
int n, m, nn, l, r, x, idx[1048576];
void index_tree(int left, int right, int now)
{
int mid;
if(l<=left && right<=r)
{
if(idx[now]<x+left-l)
idx[now]=x+left-l;
}
else
{
mid=(left+right)/2;
if(l<=mid)
index_tree(left,mid,2*now);
if(mid+1<=r)
index_tree(mid+1,right,2*now+1);
}
}
void input(void)
{
int i;
scanf("%d %d",&n,&m);
for(nn=1 ; nn<n ; nn*=2);
for(i=1 ; i<=m ; i++)
{
scanf("%d %d %d",&l,&r,&x);
index_tree(1,nn,1);
}
}
void clean(int left, int right, int now)
{
int mid=(left+right)/2;
if(left<right)
{
if(idx[now]>0)
{
if(idx[2*now]<idx[now])
idx[2*now]=idx[now];
if(idx[2*now+1]<idx[now]+mid-left+1)
idx[2*now+1]=idx[now]+mid-left+1;
}
clean(left,mid,2*now);
clean(mid+1,right,2*now+1);
}
}
void output(void)
{
int i;
for(i=nn ; i<=nn+n-1 ; i++)
printf("%d ",idx[i]);
}
int main(void)
{
int i;
input();
clean(1,nn,1);
output();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5184 KB |
Output is correct |
2 |
Correct |
0 ms |
5184 KB |
Output is correct |
3 |
Correct |
0 ms |
5184 KB |
Output is correct |
4 |
Correct |
0 ms |
5184 KB |
Output is correct |
5 |
Correct |
0 ms |
5184 KB |
Output is correct |
6 |
Correct |
0 ms |
5184 KB |
Output is correct |
7 |
Correct |
112 ms |
5184 KB |
Output is correct |
8 |
Correct |
136 ms |
5184 KB |
Output is correct |
9 |
Correct |
140 ms |
5184 KB |
Output is correct |
10 |
Correct |
152 ms |
5184 KB |
Output is correct |
11 |
Correct |
160 ms |
5184 KB |
Output is correct |
12 |
Correct |
172 ms |
5184 KB |
Output is correct |
13 |
Correct |
184 ms |
5184 KB |
Output is correct |
14 |
Correct |
176 ms |
5184 KB |
Output is correct |
15 |
Correct |
200 ms |
5184 KB |
Output is correct |
16 |
Correct |
216 ms |
5184 KB |
Output is correct |
17 |
Correct |
208 ms |
5184 KB |
Output is correct |
18 |
Correct |
232 ms |
5184 KB |
Output is correct |
19 |
Correct |
216 ms |
5184 KB |
Output is correct |
20 |
Correct |
244 ms |
5184 KB |
Output is correct |