Submission #380251

#	Time	Username	Problem	Language	Result	Execution time	Memory
380251		cpp219	Trading (IZhO13_trading)	C++14	100 / 100	550 ms	45956 KiB

trading

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 3e5 + 9;
const ll inf = 1e16 + 7;

vector<LL> g[N];
ll n,st[4*N],lazy[4*N],L,R,val,m;

void Pass(ll id){
    ll t = lazy[id]; lazy[id] = 0;
    st[id*2] += t; lazy[id*2] += t;
    st[id*2 + 1] += t; lazy[id*2 + 1] += t;
}

void upd(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        if (u == v) st[id] = val,lazy[id] = val;
        else st[id] += val,lazy[id] += val;
        return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
    st[id] = max(st[id*2],st[id*2 + 1]);
}

ll Get(ll id,ll l,ll r,ll u){
    if (u < l||r < u) return -inf;
    if (l == r) return st[id];
    ll mid = (l + r)/2; Pass(id);
    return max(Get(id*2,l,mid,u),Get(id*2 + 1,mid + 1,r,u));
}

void out_seg(){
    for (ll i = 1;i <= m;i++) cout<<Get(1,1,m,i)<<" ";
    cout<<"\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= m;i++){
        cin>>L>>R>>val;
        g[L].push_back({i,val}); g[R + 1].push_back({i,-inf});
    }
    for (ll i = 1;i < 4*N;i++) st[i] = -inf;
    for (ll i = 1;i <= n;i++){
        for (auto j : g[i]){
            ll pos = j.fs,val = j.sc;
            upd(1,1,m,pos,pos,val);
        }
        cout<<max(0ll,st[1])<<" "; upd(1,1,m,1,m,1);
    }

}

Compilation message (stderr)

trading.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
trading.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
trading.cpp: In function 'int main()':
trading.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100