Submission #861034

#	Time	Username	Problem	Language	Result	Execution time	Memory
861034		Alfraganus	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	348 KiB

segments

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

#define int long long
#define endl '\n'
#define fs first
#define ss second
#define str string
#define all(a) a.begin(), a.end()
#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;
#define each(x, a) for (auto x : a)

struct SegTree {
    int size = 1;
    vector<int> mins, add;

    SegTree (int n){
        while(size < n)
            size <<= 1;
        mins.resize(size << 1, 1e9);
        add.resize(size << 1);
    }

    void set(int i, int v, int x, int lx, int rx){
        if(rx == lx + 1){
            mins[x] = min(mins[x], v);
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m)
            set(i, v, (x << 1) + 1, lx, m);
        else
            set(i, v, (x << 1) + 2, m, rx);
        mins[x] = min(mins[(x << 1) + 1] - add[(x << 1) + 1], mins[(x << 1) + 2] - add[(x << 1) + 2]);
    }

    void set(int i, int v)
    {
        set(i, v, 0, 0, size);
    }

    void push(int r, int k, int x, int lx, int rx){
        if(rx <= r){
            add[x] += k;
            return;
        }
        if(lx >= r){
            return;
        }
        int m = (lx + rx) >> 1;
        push(r, k, (x << 1) + 1, lx, m);
        push(r, k, (x << 1) + 2, m, rx);
        mins[x] = min(mins[(x << 1) + 1] - add[(x << 1) + 1], mins[(x << 1) + 2] - add[(x << 1) + 2]);
    }

    void push(int r, int k){
        push(r, k, 0, 0, size);
    }

    int ans(int x, int lx, int rx, int s = 0){
        if(rx == lx + 1){
            return lx;
        }
        s += add[x];
        int m = (lx + rx) >> 1;
        if(mins[(x << 1) + 2] - s <= 0)
            return ans((x << 1) + 2, m, rx, s);
        return ans((x << 1) + 1, lx, m, s);
    }

    int ans(){
        return ans(0, 0, size);
    }
};

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    vector<int> pre(n + 1);
    for(int i = 0; i < n; i ++)
        pre[i + 1] = pre[i] + a[i];
    SegTree s(n + 1);
    s.set(0, 0);
    vector<int> dp(n + 1), sum(n + 1);
    for(int i = 0; i < n; i ++){
        s.push(i + 1, a[i]);
        int j = s.ans();
        dp[i + 1] = dp[j] + 1;
        sum[i + 1] = pre[i + 1] - pre[j];
        s.set(i + 1, sum[i + 1]);
    }
    cout << dp[n];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

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