Submission #331546

#	Time	Username	Problem	Language	Result	Execution time	Memory
331546		limabeans	Bigger segments (IZhO19_segments)	C++17	100 / 100	87 ms	18924 KiB

segments

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 1e18;


const int maxn = 5e5 + 10;



int n;
ll a[maxn];
ll pre[maxn];
ll dp[maxn];
int pos[maxn];

ll qry(int l, int r) {
    assert(l<=r);
    return pre[r]-pre[l-1];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    for (int i=1; i<=n; i++) {
	pre[i]=pre[i-1]+a[i];
    }

    for (int i=1; i<=n; i++) {
	pos[i]=max(pos[i],pos[i-1]);
	dp[i]=1+dp[pos[i]];

	int lo=i;
	int hi=n+1;
	int p=-1;
	while (hi-lo>1) {
	    int mid=(lo+hi)/2;
	    if (qry(pos[i]+1,i)<=qry(i+1,mid)) {
		hi=mid;
		p=mid;
	    } else {
		lo=mid;
	    }
	}
	if (~p) {
	    pos[p]=i;
	}
    }

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

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