Submission #1198448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198448		TheSahib	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	320 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Fenwick tree for range‐maximum queries
struct Fenwick {
    int n;
    vector<int> f;
    Fenwick(int _n): n(_n), f(n+1, 0) {}
    // point update: set f[i] = max(f[i], v)
    void update(int i, int v) {
        for(; i <= n; i += i & -i)
            f[i] = max(f[i], v);
    }
    // prefix query: max over f[1..i]
    int query(int i) const {
        int r = 0;
        for(; i > 0; i -= i & -i)
            r = max(r, f[i]);
        return r;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> a(N), S(N+1, 0);
    for(int i = 0; i < N; i++){
        cin >> a[i];
        S[i+1] = S[i] + a[i];
    }

    // 1) coordinate‐compress all prefix‐sums S[0..N]
    vector<ll> all = S;
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    auto idx = [&](ll x){
        return int(lower_bound(all.begin(), all.end(), x) - all.begin()) + 1;
    };

    // 2) bestSum[d] = minimum prefix‐sum S[j] at which we can form d segments
    vector<ll> bestSum(N+2, LLONG_MAX);
    bestSum[0] = 0;

    // 3) Fenwick tree will store, for each “key” K_j = 2*S[j] - bestSum[d_j], the value d_j
    //    so that querying up to S[i] gives the max d_j with K_j <= S[i].
    //    Because K_j may not be in our compressed array, we’ll separately compress the set of
    //    all possible keys as we go, by inserting (2*S[j] - bestSum[d_j]) into a second list.
    //
    //    But we can avoid a second compression if we notice that:
    //       K_j <= S[i]
    //       ⇔ 2*S[j] - bestSum[d_j] <= S[i]
    //       ⇔ S[j] <= (S[i] + bestSum[d_j]) / 2
    //
    //    However, that mixes d_j inside the bound, so we still need the original trick.
    //
    // For clarity and speed in contest, here’s the standard two‐Fenwick approach:

    // Prepare to collect all keys
    vector<ll> keys;
    keys.reserve(N+1);
    // initial j=0: d_j=0, bestSum[0]=0 -> key = 2*S[0] - 0 = 0
    keys.push_back(0);
    for(int j = 1; j <= N; j++){
        // we’ll later fill in key for each j once we know d_j
        // but for size we can push a placeholder
        keys.push_back(0);
    }

    // we will fill keys[j] = 2*S[j] - bestSum[d_j] after we compute d_j,
    // so let's do that on the fly, but we need the Fenwick size upfront:
    // to be safe, we’ll just compress over the union of all S[] and all (2*S[j]-anything),
    // but that’s tricky. Instead, we’ll do this:
    // — first pass: assume d_j <= N, bestSum[d_j] <= max S, so key <= 2*maxS.
    // — we can compress the range [minKey..maxKey] by noticing it’s still O(N).
    //
    // Actually the simplest is: we know every time we update bestSum[d+1] = S[i], the
    //   corresponding key = 2*S[i] - bestSum[d] is ≥ S[i] (since bestSum[d] ≤ S[i]).
    //   So all keys we ever produce lie in [min S .. 2*max S].
    // We can collect them in a vector during the loop, then rebuild Fenwick.

    // Instead, let's do two‐pass:
    // Pass 1: compute dp_i and bestSum, collect keys.
    // Pass 2: compress keys and replay updates into Fenwick to answer.

    // PASS 1: compute dp_i and bestSum, collect raw key values
    vector<int> dp(N+1, 0);
    for(int i = 1; i <= N; i++){
        // find best d with bestSum[d] <= S[i] by binary search
        int lo = 0, hi = i;
        while(lo < hi){
            int mid = (lo + hi + 1) >> 1;
            if(bestSum[mid] <= S[i]) lo = mid;
            else hi = mid - 1;
        }
        dp[i] = lo;
        // update bestSum for d+1
        bestSum[lo+1] = min(bestSum[lo+1], S[i]);
        // record the key for this j=i
        ll key = 2*S[i] - bestSum[lo];
        keys[i] = key;
    }

    // Now compress all unique key values alongside S[i]
    vector<ll> allKeys = keys;
    sort(allKeys.begin(), allKeys.end());
    allKeys.erase(unique(allKeys.begin(), allKeys.end()), allKeys.end());
    auto keyIdx = [&](ll x){
        return int(lower_bound(allKeys.begin(), allKeys.end(), x) - allKeys.begin()) + 1;
    };

    // Build Fenwick over key‐indices
    Fenwick fenw((int)allKeys.size());

    // Re‐initialize bestSum & answer, then replay
    fill(bestSum.begin(), bestSum.end(), LLONG_MAX);
    bestSum[0] = 0;
    int answer = 0;

    // j=0 initial state
    fenw.update(keyIdx(0), 0);

    for(int i = 1; i <= N; i++){
        // dp_i is exactly the best we can get by querying all keys ≤ S[i]
        // i.e. find the last key-value index such that key ≤ S[i]
        int pos = int(upper_bound(allKeys.begin(), allKeys.end(), S[i]) - allKeys.begin());
        int bestd = fenw.query(pos);
        answer = max(answer, bestd);

        // now update for j=i: we can form bestd+1 segments ending here
        // key = keys[i]
        int kpos = keyIdx(keys[i]);
        fenw.update(kpos, bestd+1);
    }

    cout << answer << "\n";
    return 0;
}

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