#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> matrix;
struct ragetree {
int lazy[1200000];
int sz;
ragetree() {
for(int i = 1; i < 1200000; i++) lazy[i] = -1e9;
sz = 300000;
}
void update(int idx, int l, int r, int lhs, int rhs, int v) {
if(l >= lhs && r <= rhs) {
lazy[idx] = max(lazy[idx], v);
return;
}
lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
int m = (l+r)/2;
if(m >= lhs) update(2*idx, l, m, lhs, rhs, v);
if(m+1 <= rhs) update(2*idx+1, m+1, r, lhs, rhs, v);
}
void update(int l, int r, int v) {
update(1, 1, sz, l, r, v);
}
void solve(int idx, int l, int r, vector<int>& ret) {
if(l == r) {
ret.push_back(max(0, l + lazy[idx]));
return;
}
lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
int m = (l+r)/2;
solve(2*idx, l, m, ret);
solve(2*idx+1, m+1, r, ret);
}
void solve(vector<int>& ret) {
solve(1, 1, sz, ret);
}
};
ragetree rt;
void solve() {
int n, m;
cin >> n >> m;
while(m--) {
int l, r, x;
cin >> l >> r >> x;
rt.update(l, r, x-l);
}
vector<int> ret;
rt.solve(ret);
for(int i = 1; i <= n; i++) {
cout << ret[i-1];
if(i == n) cout << endl;
else cout << " ";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7408 KB |
Output is correct |
2 |
Correct |
9 ms |
7524 KB |
Output is correct |
3 |
Correct |
9 ms |
7524 KB |
Output is correct |
4 |
Correct |
9 ms |
7552 KB |
Output is correct |
5 |
Correct |
9 ms |
7728 KB |
Output is correct |
6 |
Correct |
10 ms |
7876 KB |
Output is correct |
7 |
Correct |
102 ms |
10764 KB |
Output is correct |
8 |
Correct |
113 ms |
14180 KB |
Output is correct |
9 |
Correct |
121 ms |
17392 KB |
Output is correct |
10 |
Correct |
134 ms |
20848 KB |
Output is correct |
11 |
Correct |
138 ms |
25100 KB |
Output is correct |
12 |
Correct |
139 ms |
28968 KB |
Output is correct |
13 |
Correct |
155 ms |
33408 KB |
Output is correct |
14 |
Correct |
149 ms |
37420 KB |
Output is correct |
15 |
Correct |
169 ms |
42468 KB |
Output is correct |
16 |
Correct |
182 ms |
47248 KB |
Output is correct |
17 |
Correct |
178 ms |
52384 KB |
Output is correct |
18 |
Correct |
185 ms |
57772 KB |
Output is correct |
19 |
Correct |
177 ms |
62732 KB |
Output is correct |
20 |
Runtime error |
216 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |