Submission #424796

#	Time	Username	Problem	Language	Result	Execution time	Memory
424796		doowey	Bigger segments (IZhO19_segments)	C++14	100 / 100	221 ms	36444 KiB

segments

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 10;
const ll inf = (ll)1e18;
ll A[N];
ll P[N];
ll dp[N];
ll sum[N];

ll val[N * 4 + 512];

int fin(int node, int cl, int cr, ll F){
    if(cl == cr){
        return cl;
    }
    int mid = (cl + cr) / 2;
    if(val[node * 2 + 1] <= F){
        return fin(node * 2 + 1, mid + 1, cr, F);
    }
    else{
        return fin(node * 2, cl, mid, F);
    }
}

void update(int node, int cl, int cr, int id, ll v){
    if(cl == cr){
        val[node] = v;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        update(node * 2, cl, mid, id, v);
    else
        update(node * 2 + 1, mid + 1, cr, id, v);
    val[node] = min(val[node * 2], val[node * 2 + 1]);
}


int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    for(int i = 1; i <= N * 4 + 128; i ++ ){
        val[i] = inf;
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        P[i] = A[i] + P[i - 1];
    }
    update(1, 0, n, 0, 0);
    int idx;
    for(int i = 1; i <= n; i ++ ){
        idx = fin(1, 0, n, P[i]);
        dp[i] = dp[idx] + 1;
        sum[i] = P[i] - P[idx];
        update(1, 0, n, i, sum[i]+P[i]);
    }
    cout << dp[n] << "\n";
    return 0;
}

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