oj.uz

Submission #756685

# Submission time Handle Problem Language Result Execution time Memory
756685 2023-06-12T05:03:04 Z otarius Trading (IZhO13_trading) C++17
100 / 100
 331 ms 13296 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]);
    } lazy[v] = 0;
}
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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 472 KB Output is correct
7 Correct 141 ms 6656 KB Output is correct
8 Correct 221 ms 8248 KB Output is correct
9 Correct 170 ms 7420 KB Output is correct
10 Correct 178 ms 6092 KB Output is correct
11 Correct 209 ms 8912 KB Output is correct
12 Correct 215 ms 7692 KB Output is correct
13 Correct 272 ms 8760 KB Output is correct
14 Correct 218 ms 7668 KB Output is correct
15 Correct 252 ms 8980 KB Output is correct
16 Correct 276 ms 8996 KB Output is correct
17 Correct 261 ms 11232 KB Output is correct
18 Correct 282 ms 12736 KB Output is correct
19 Correct 276 ms 10968 KB Output is correct
20 Correct 331 ms 13296 KB Output is correct