#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define mid (r + l)/2
#define N 100005
#define maxc 1000000007
using namespace std;
int n, m;
struct IntervalTree
{
int t[N << 2];
void build()
{
for (int i = 0; i < (N << 2); i++)
t[i] = -maxc;
}
void update(int l, int r, int id, int x, int y, int val)
{
if (l > y || r < x) return;
if (l >= x && r <= y)
{
t[id] = max(t[id], val);
return;
}
update(l, mid, id*2, x, y, val);
update(mid+1, r, id*2+1, x, y, val);
}
int get(int l, int r, int id, int x)
{
if (l > x || r < x) return -maxc;
if (l == r)
return t[id];
int z = t[id];
int a = get(l, mid, id*2, x);
int b = get(mid+1, r, id*2+1, x);
return max({z, a, b});
}
}t;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
cin >> n >> m;
t.build();
for (int i = 1; i <= m; i++)
{
int u, v, w; cin >> u >> v >> w;
w -= (u-1);
t.update(1, n, 1, u, v, w);
}
for (int i = 1; i <= n; i++)
{
int res = t.get(1, n, 1, i);
if (res == -maxc) cout <<0<<" ";
else cout <<t.get(1, n, 1, i) + i - 1<<" ";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
2024 KB |
Output is correct |
3 |
Correct |
3 ms |
2024 KB |
Output is correct |
4 |
Correct |
4 ms |
2048 KB |
Output is correct |
5 |
Correct |
4 ms |
2092 KB |
Output is correct |
6 |
Correct |
5 ms |
2260 KB |
Output is correct |
7 |
Runtime error |
5 ms |
3996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |