Submission #357740

#	Time	Username	Problem	Language	Result	Execution time	Memory
357740		nicolaalexandra	Divide and conquer (IZhO14_divide)	C++14	100 / 100	150 ms	6892 KiB

divide

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000000000000LL
using namespace std;

long long aint[DIM*5],sp[DIM],sp_g[DIM];
int n,i,x,sol;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = INF;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = INF;
}

void update (int nod, int st, int dr, int poz, long long val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = min (aint[nod<<1],aint[(nod<<1)|1]);
}

void query (int nod, int st, int dr, int x, int y, long long val){
    if (sol)
        return;
    if (x <= st && dr <= y){

        if (aint[nod] <= val){

            if (st == dr)
                sol = st;
            else {
                int mid = (st+dr)>>1;
                if (aint[nod<<1] <= val)
                    query (nod<<1,st,mid,x,y,val);
                else query ((nod<<1)|1,mid+1,dr,x,y,val);
            }

        }

        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y,val);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y,val);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;

    build (1,1,n);

    long long ans = 0;
    for (i=1;i<=n;i++){
        cin>>x>>sp_g[i]>>sp[i];
        sp[i] += sp[i-1];
        sp_g[i] += sp_g[i-1];

        update (1,1,n,i,sp[i-1] - x);

        sol = 0;
        query (1,1,n,1,i,sp[i] - x);
        if (sol)
            ans = max (ans,sp_g[i] - sp_g[sol-1]);
    }

    cout<<ans;

    return 0;
}

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