Submission #1053065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053065		kachim2	Trading (IZhO13_trading)	C++17	100 / 100	70 ms	12116 KiB

trading

#include<bits/stdc++.h>
using namespace std;
int nin(){
    int x;
    cin >> x;
    return x;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    const int n = nin(), m = nin();
    vector<int> segtree(1<<20, INT_MIN);
    auto update = [&segtree](int l, int r, int v){
        const int base = segtree.size()/2;
        l+=base;
        r+=base;
        l--;
        r++;
        while(r-l>1){
            segtree[r-1]=max(segtree[r-1], v);
            segtree[l+1]=max(segtree[l+1], v);
            l/=2;
            r/=2;
        }

    };
    auto query = [&segtree](int n){
        const int base = segtree.size()/2;
        n+=base;
        int ret = INT_MIN;
        while (n!=0)
        {
            ret = max(ret, segtree[n]);
            n/=2; 
        }
        return ret;
        
    };
    for(int i = 0; i < m; i++){
        const int l = nin(), r = nin();

        const int v = nin()-l;
        update(l, r, v);
    }
    for(int i = 1; i <= n; i++){
        cout << max(0, query(i)+i) << ' ';
    }

}

• Subtask 1: 100 / 100