oj.uz

Submission #673593

# Submission time Handle Problem Language Result Execution time Memory
673593 2022-12-21T08:40:04 Z moday_morning Trading (IZhO13_trading) C++17
100 / 100
 167 ms 13620 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500005;

int n, m, l, r, x, seg[4 * N], ans[N];
void update (int node, int L, int R, int l, int r) {
    if (L > r || l > R) {
        return;
    }
    if (l <= L && r >= R) {
        seg[node] = max(seg[node], x);
        return;
    }
    int mid = (L + R)/2;
    update(node * 2, L, mid, l, r);
    update(node * 2 + 1, mid + 1, R, l, r);
}
void res (int node, int l, int r) {
    if (l == r){
        ans[l] = seg[node];
        return;
    }
    int mid = (l + r)/2;
    seg[node * 2] = max(seg[node], seg[node * 2]);
    res(node * 2, l, mid);
    seg[node * 2 + 1] = max(seg[node], seg[node * 2 + 1]);
    res(node * 2 + 1, mid + 1, r);
}

void solve () {
    cin >> n>> m;
    for (int i = 0;i < 4 * n;i++) seg[i] = -1e9;
    while (m--){
        cin >> l>> r>> x;
        x -= (l - 1);
        update(1, 1, n, l, r);
    }
    res(1, 1, n);
    for (int i = 0; i < n; i++) {
        cout << max(ans[i + 1] + i, 0LL) << " ";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 92 ms 6944 KB Output is correct
8 Correct 91 ms 7952 KB Output is correct
9 Correct 105 ms 8100 KB Output is correct
10 Correct 101 ms 8464 KB Output is correct
11 Correct 104 ms 9744 KB Output is correct
12 Correct 117 ms 9632 KB Output is correct
13 Correct 130 ms 10560 KB Output is correct
14 Correct 118 ms 10660 KB Output is correct
15 Correct 137 ms 11396 KB Output is correct
16 Correct 145 ms 11528 KB Output is correct
17 Correct 136 ms 11968 KB Output is correct
18 Correct 146 ms 12372 KB Output is correct
19 Correct 141 ms 12828 KB Output is correct
20 Correct 167 ms 13620 KB Output is correct