Submission #410662

#	Time	Username	Problem	Language	Result	Execution time	Memory
410662		8e7	Bigger segments (IZhO19_segments)	C++14	100 / 100	98 ms	16964 KiB

segments

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <set>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define maxn 500005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll pref[maxn], dp[maxn], from[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> pref[i], pref[i] += pref[i - 1];	
	for (int i = 1;i <= n;i++) {
		if (from[i - 1] > from[i]) from[i] = from[i - 1];
		dp[i] = dp[from[i]] + 1;
		int id = lower_bound(pref, pref + n + 1, 2 * pref[i] - pref[from[i]]) - pref;
		if (i > from[id]) from[id] = i;
	}
	cout << dp[n] << "\n";
}

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