Submission #1006290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006290		Owen11	Bigger segments (IZhO19_segments)	C++14	100 / 100	280 ms	47332 KiB

segments

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

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

void solve() {
    int n; cin >> n;

    int num[n+5];
    int dp[n+5]; dp[0] = 0;
    int pos[n+5];
    memset(pos, 0, sizeof(pos));
    int pre[n+5]; pre[0] = 0; pre[n+1] = 1e18;
    set<pair<int, int>> st;

    for(int i = 1; i<=n; i++) cin >> num[i];
    for(int i = 1; i<=n; i++) pre[i] = pre[i-1]+num[i];
    for(int i = 1; i<=n; i++) st.insert({pre[i], i});
    st.insert({pre[n+1], n+1});

    for(int i = 1; i<=n; i++) {
        pos[i] = max(pos[i], pos[i-1]);
        dp[i] = dp[pos[i]]+1;
        pair<int, int> x = *st.lower_bound({2*pre[i]-pre[pos[i]], 0});
        pos[x.sec] = i;
    }

    cout << dp[n] << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

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