제출 #1131382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131382		sofija6	Divide and conquer (IZhO14_divide)	C++20	100 / 100	163 ms	28744 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define llinf 1e16
using namespace std;
ll n,ans,x[MAXN],g[MAXN],d[MAXN],sz;
set<ll> s;
struct seg_tree
{
    vector<ll> st;
    void Init()
    {
        sz=1;
        while (sz<2*n)
            sz <<= 1;
        st.resize(2*sz+2,llinf);
    }
    void Update(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]=min(st[x],val);
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Update(pos,val,2*x,lx,mid);
        else
            Update(pos,val,2*x+1,mid+1,rx);
        st[x]=min(st[2*x],st[2*x+1]);
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return llinf;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return min(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
map<ll,ll> val;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (ll i=1;i<=n;i++)
    {
        cin >> x[i] >> g[i] >> d[i];
        d[i]+=d[i-1];
        g[i]+=g[i-1];
        s.insert(d[i]-x[i]);
        s.insert(d[i-1]-x[i]);
    }
    ll cnt=1;
    for (auto i : s)
        val[i]=cnt++;
    S.Init();
    for (ll i=1;i<=n;i++)
    {
        ans=max(ans,g[i]-S.Calc(1,val[d[i]-x[i]],1,1,sz));
        S.Update(val[d[i-1]-x[i]],g[i-1],1,1,sz);
        ans=max(ans,g[i]-g[i-1]);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52