#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 3e5 + 5;
int n, m;
int l[N], r[N], a[N], ans[N];
vector < int > event[N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d", l + i, r + i, a + i);
event[l[i]].push_back(i);
event[r[i] + 1].push_back(-i);
}
multiset < int > s;
for(int i = 1; i <= n; i++) {
foreach(it, event[i]) {
int x = *it;
if(x > 0) {
s.insert(l[x] - a[x]);
}
else {
x = -x;
s.erase(s.find(l[x] - a[x]));
}
}
if(s.empty())
continue;
ans[i] = -*s.begin() + i;
}
for(int i = 1; i <= n; i++)
printf("%d ", ans[i]);
puts("");
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
13444 KB |
Output is correct |
2 |
Correct |
0 ms |
13444 KB |
Output is correct |
3 |
Correct |
0 ms |
13444 KB |
Output is correct |
4 |
Correct |
4 ms |
13444 KB |
Output is correct |
5 |
Correct |
0 ms |
13444 KB |
Output is correct |
6 |
Correct |
6 ms |
13444 KB |
Output is correct |
7 |
Correct |
177 ms |
19520 KB |
Output is correct |
8 |
Correct |
185 ms |
20696 KB |
Output is correct |
9 |
Correct |
212 ms |
21000 KB |
Output is correct |
10 |
Correct |
256 ms |
21600 KB |
Output is correct |
11 |
Correct |
205 ms |
21660 KB |
Output is correct |
12 |
Correct |
286 ms |
23604 KB |
Output is correct |
13 |
Correct |
277 ms |
21804 KB |
Output is correct |
14 |
Correct |
288 ms |
22480 KB |
Output is correct |
15 |
Correct |
313 ms |
23332 KB |
Output is correct |
16 |
Correct |
380 ms |
21908 KB |
Output is correct |
17 |
Correct |
331 ms |
23240 KB |
Output is correct |
18 |
Correct |
376 ms |
26480 KB |
Output is correct |
19 |
Correct |
363 ms |
23064 KB |
Output is correct |
20 |
Correct |
401 ms |
24684 KB |
Output is correct |