Submission #371430

#	Time	Username	Problem	Language	Result	Execution time	Memory
371430		nicolaalexandra	Bigger segments (IZhO19_segments)	C++14	100 / 100	337 ms	21356 KiB

segments

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

int v[DIM],dp[DIM],poz[DIM];
long long sp[DIM],aint[DIM*4];
int n,i,sol;

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

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, long long val){
    if (st == dr){
        if (aint[nod] <= val)
            sol = st;
        return;
    }
    int mid = (st+dr)>>1;
    if (aint[(nod<<1)|1] <= val)
        query ((nod<<1)|1,mid+1,dr,val);
    else query ((nod<<1),st,mid,val);
}

int main (){

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

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }

    build (1,1,n);

    for (i=1;i<=n;i++){
        sol = 0;
        query (1,1,n,sp[i]);

        dp[i] = dp[sol] + 1;
        update (1,1,n,i,2*sp[i]-sp[sol]);
    }

    cout<<dp[n];

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27