Submission #175805

#	Time	Username	Problem	Language	Result	Execution time	Memory
175805		_Enkognit	Divide and conquer (IZhO14_divide)	C++14	100 / 100	341 ms	11384 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pll pair<ll,ll>
#define y1 Enkognit
#define fi first
#define se second
#define pld pair<ld,ld>

using namespace std;

const ll MOD=1000000007;

ll l, r, n, m, k, y, leaf[10000001], a[1000001], x[1000001], b[1000001];
ll tt[10000001];
vector <ll> an;

ll binpow(ll h,ll r)
{
    ll l=1;
    while (r)
    {
        if (r&1) l*=h,l%=MOD;
        h*=h;
        h%=MOD;
        r/=2;
    }
    return l;
}

ll d[10000001];

void push(int h)
{
    if (leaf[h]) return;
    if (tt[h])
    {
        d[h*2]+=tt[h];
        tt[h*2]+=tt[h];
        d[h*2+1]+=tt[h];
        tt[h*2+1]+=tt[h];
        tt[h]=0;
    }
}

void build(int h,int l,int r)
{
    if (l==r) {leaf[h]=1;d[h]=-1;return;}
    int w=(l+r)/2;
    build(h*2,l,w);
    build(h*2+1,w+1,r);
    d[h]=-1;
}

void update(int h,int l,int r,int x,int y,int k)
{
    //cout << l << " " << x << " " << y << " " << r << "\n";
    push(h);
    if (x>y) return;
    if (l==x && y==r)
    {
        d[h]+=k;
        tt[h]+=k;
        push(h);
        return;
    }
    int w=(l+r)/2;
    update(h*2,l,w,x,min(y,w),k);
    update(h*2+1,w+1,r,max(x,w+1),y,k);
    d[h]=max(d[h*2],d[h*2+1]);
}

ll get(int h,int l,int r)
{
    push(h);
    if (l==r) return l;
    int w=(l+r)/2;
    if (d[h*2]>=0) return get(h*2,l,w); else return get(h*2+1,w+1,r);
}

int main()
{
    //ios::sync_with_stdio(0);
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        cin >> x[i] >> b[i] >> a[i];
        b[i]+=b[i-1];
    }
    ll ans=0;
    build(1,1,n);
    for (int i = 1; i <= n; i++)
    {
        update(1,1,n,i,i,1);
        //cout << i << "\n";
        update(1,1,n,1,i,a[i]);
        update(1,1,n,1,i-1,x[i-1]-x[i]);
        ans=max(ans,b[i]-b[get(1,1,n)-1]);
    }
    cout << ans;
    return 0;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/

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