Submission #268614

#	Time	Username	Problem	Language	Result	Execution time	Memory
268614		Osama_Alkhodairy	Bigger segments (IZhO19_segments)	C++17	37 / 100	1581 ms	17132 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 500001;
const ll INF = 1e18;

int n;
vector <int> a;
ll dp[N], tree[4 * N], lazy[4 * N];

void push(int l, int r, int node){
    tree[node] += lazy[node];
    if(l != r){
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}
void update(int l, int r, int node, int s, int e, ll v){
    if(r < l) return;
    push(l, r, node);
    if(r < s || l > e) return;
    if(s <= l && r <= e){
        lazy[node] += v;
        push(l, r, node);
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, 2 * node, s, e, v);
    update(mid + 1, r, 2 * node + 1, s, e, v);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query(int l, int r, int node, int p){
    if(r < l || l > p) return -1;
    push(l, r, node);
    if(r <= p && tree[node] > 0) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = query(mid + 1, r, 2 * node + 1, p);
    if(ret != -1) return ret;
    return query(l, mid, 2 * node, p);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0 ; i < 4 * N ; i++){
        tree[i] = INF;
    }
    cin >> n;
    a.resize(n + 1);
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for(int i = 1 ; i <= n ; i++){
        ll sum = 0;
        for(int j = i ; j >= 1 ; j--){
            sum += a[j];
            if(sum >= dp[j - 1]){
                dp[i] = sum;
                break;
            }
        }
    }
    update(0, n, 1, 0, 0, -INF);
    vector <int> ans(n + 1);
    for(int i = 1 ; i <= n ; i++){
        update(0, n, 1, 0, i - 1, -a[i]);
        int idx = query(0, n, 1, i - 1);
        ans[i] = ans[idx] + 1;
        update(0, n, 1, i, i, -INF + dp[i]);
    }
    cout << ans[n] << endl;
}

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