Submission #380264

#	Time	Username	Problem	Language	Result	Execution time	Memory
380264		Aryan_Raina	Trading (IZhO13_trading)	C++14	100 / 100	279 ms	10604 KiB

trading

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array

const int INF = 1e17;
const int MOD = 1e9;

struct SegTree {
    vector<int> values;
    int size;
    void init(int n) {
        size = 1;
        while (size < n) size <<= 1;
        values.resize(2*size);
    }
    void modify(int l, int r, int v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) return;
        if (l <= lx && rx <= r) {
            values[x] = max(values[x], v + (lx - l));
            //cout<<lx<<" "<<rx<<" "<<values[x]<<endl;
            return;
        }
        int m = (lx + rx) >> 1;
        modify(l, r, v, 2*x + 1, lx, m);
        modify(l, r, v, 2*x + 2, m, rx);
    }
    void modify(int l, int r, int v) {
        modify(l, r, v, 0, 0, size);
    }
    int get(int i, int x, int lx, int rx) { 
        if (rx - lx == 1) return values[x];
        int m = (lx + rx) >> 1;
        int ans = 0;
        if (i < m) {
            ans = get(i, 2*x+1, lx, m);
        } else {
            ans = get(i, 2*x+2, m, rx);
        }
        if (values[x]) ans = max(ans, values[x] + i-lx);
        return ans;
    }
    int get(int i) {
        return get(i, 0, 0, size);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin>>n>>m;
    SegTree st; st.init(n);
    for (int i = 0; i < m; i++) {
        int l, r, v; cin>>l>>r>>v; --l, --r;
        st.modify(l, r+1, v);
    }
    for (int i = 0; i < n; i++) cout<<st.get(i)<<" ";
}

• Subtask 1: 100 / 100