Submission #685517

#	Time	Username	Problem	Language	Result	Execution time	Memory
685517		Ronin13	Trading (IZhO13_trading)	C++14	100 / 100	391 ms	26432 KiB

trading

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 3e5 + 1;

vector <int> t(4 * nmax, -INT_MAX);
void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = max(t[v], val);
        return;
    }
    int m= (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v  +1, m + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return -INT_MAX;
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) / 2;
    int x = get(2 * v, l, m, st, fin);
    int y = get(2 * v + 1, m+ 1, r, st, fin);
    return max(x, y);
}

int main(){
    int n; cin >> n;
    int ans[n + 1];
    fill(ans, ans + n + 1, 0);
    int m; cin >> m;
    vector <vector <pii> > vec(n + 1);
    for(int i = 1; i <= m; i++){
        int l, r, x; cin >> l >> r >> x;
        vec[l].pb({r, x});
    }
    for(int i = 1; i <= n; i++){
        for(auto to : vec[i]){
            int r = to.f, val = to.s;
            update(1, 1, n, r, val - i);
        }
        int v = get(1, 1, n, i, n);
        ans[i] = max(ans[i], v + i);
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

• Subtask 1: 100 / 100