Submission #1037063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037063		vjudge1	Trading (IZhO13_trading)	C++17	100 / 100	243 ms	20648 KiB

trading

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
vector<ll> st, L;
void Input(){
    cin>>n>>m;
    st.resize(4*n + 7,0);
    L.resize(4*n + 7,0);
}
void Fix(int id, int l, int r){
    if(!L[id]) return;

    st[id] = max(st[id], L[id]);
    if(l != r){
        int m = (l + r)/2;
        L[2*id] = max(L[2*id], L[id]);
        L[2*id + 1] = max(L[2*id + 1],L[id] + m + 1 - l);
    }
    L[id] = 0;
}
void Update(int id, int l, int r, int u, int v, ll val){
    Fix(id,l,r);
    if(v < l || r < u) return;
    if(u <= l && r <= v){
        L[id] = max(L[id], val + (l - u));
        return;
    }
    int m = (l + r)/2;
    Update(2*id,l,m,u,v,val);
    Update(2*id + 1,m + 1, r, u, v, val);
    st[id] = max(st[2*id], st[2*id + 1]);
}
ll Get(int id, int l, int r, int u, int v){
    Fix(id,l,r);
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[id];
    int m = (l + r)/2;
    return max(Get(2*id,l,m,u,v), Get(2*id + 1, m + 1,r,u,v));
}
void Build(){
    for(int i = 1; i <= m; ++i){
        int l,r;
        ll x;
        cin>>l>>r>>x;
        Update(1,1,n,l,r,x);
    }
}
void Output(){
    Build();
    for(int i = 1; i <= n; ++i) cout<<Get(1,1,n,i,i)<<" ";
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    Input();
    Output();
    return 0;
}

• Subtask 1: 100 / 100