Submission #756685

#	Time	Username	Problem	Language	Result	Execution time	Memory
756685		otarius	Trading (IZhO13_trading)	C++17	100 / 100	331 ms	13296 KiB

trading

#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 / 100