oj.uz

Submission #755438

# Submission time Handle Problem Language Result Execution time Memory
755438 2023-06-10T06:06:51 Z otarius Trading (IZhO13_trading) C++17
100 / 100
 346 ms 13244 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define sc second
#define ll long long
#define pii pair<int, int>

int t[1200005], lazy[1200005];
void prop(int v, int tl, int tr) {
    t[v] = max(t[v], lazy[v]);
    if (tl != tr) {
        int tm = (tl + tr) / 2;
        lazy[2 * v] = max(lazy[2 * v], lazy[v] - tr + tm);
        lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
    }
}
void update(int v, int tl, int tr, int l, int r, int x) {
    if (lazy[v])
        prop(v, tl, tr);
    if (tr < l || tl > r)
        return;
    if (l <= tl && tr <= r) {
        t[v] = max(t[v], x + tr - l);
        if (tl != tr) {
            int tm = (tl + tr) / 2;
            lazy[2 * v] = max(lazy[2 * v], x + tm - tl);
            lazy[2 * v + 1] = max(lazy[2 * v + 1], x + tr - tl);
        }
        return;
    } int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, min(r, tm), x);
    if (l >= tm + 1)
        update(2 * v + 1, tm + 1, tr, l, r, x);
    else update(2 * v + 1, tm + 1, tr, tm + 1, r, x + tm + 1 - l);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
int getans(int v, int tl, int tr, int pos) {
    if (lazy[v])
        prop(v, tl, tr);
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return getans(2 * v, tl, tm, pos);
    else return getans(2 * v + 1, tm + 1, tr, pos);
}
void solve() {
    int n, m;
    cin >> n >> m;
    int l, r, x;
    while (m--) {
        cin >> l >> r >> x;
        update(1, 1, n, l, r, x);
    } for (int i = 1; i <= n; i++)
        cout << getans(1, 1, n, i) << ' ';
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 159 ms 6740 KB Output is correct
8 Correct 228 ms 8360 KB Output is correct
9 Correct 173 ms 7568 KB Output is correct
10 Correct 197 ms 6092 KB Output is correct
11 Correct 205 ms 8908 KB Output is correct
12 Correct 250 ms 7792 KB Output is correct
13 Correct 236 ms 8780 KB Output is correct
14 Correct 234 ms 7628 KB Output is correct
15 Correct 271 ms 9076 KB Output is correct
16 Correct 276 ms 8908 KB Output is correct
17 Correct 325 ms 11316 KB Output is correct
18 Correct 272 ms 12620 KB Output is correct
19 Correct 346 ms 10908 KB Output is correct
20 Correct 313 ms 13244 KB Output is correct