#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define sz(s) (int)(s.size())
#define eb emplace_back
#define mkp make_pair
#define all(x) x.begin(), x.end()
const int N = 2e5 + 500;
const int NN = 4e3;
int a[N];
vector <int> v[N];
set <pair <int, int>> st;
int x[N], l[N], r[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++ i) {
cin >> l[i] >> r[i] >> x[i];
v[l[i]].eb(i);
int pos = -i;
v[r[i] + 1].eb(pos);
}
/*for (int i = 1; i <= n; ++ i) {
cerr << i << ": ";
for (auto to : v[i])
cerr << to << " ";
cerr << '\n';
}*/
for (int i = 1; i <= n; ++ i) {
int res = 0;
for (auto to : v[i]) {
int dif = x[to] - l[to];
int pos = -to;
int dif2 = x[pos] - l[pos];
if (to <= 0)
st.erase(mkp(dif2, pos));
if (to >= 1)
st.insert(mkp(dif, to));
}
if (!st.empty()) {
res = (--st.end()) -> first + i;
}
cout << res << " ";
}
}
int main () {
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5112 KB |
Output is correct |
4 |
Correct |
7 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
5240 KB |
Output is correct |
6 |
Correct |
12 ms |
5240 KB |
Output is correct |
7 |
Correct |
397 ms |
13848 KB |
Output is correct |
8 |
Correct |
487 ms |
15456 KB |
Output is correct |
9 |
Correct |
478 ms |
16012 KB |
Output is correct |
10 |
Correct |
547 ms |
16380 KB |
Output is correct |
11 |
Correct |
504 ms |
17136 KB |
Output is correct |
12 |
Runtime error |
416 ms |
24372 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |