Submission #497742

#	Time	Username	Problem	Language	Result	Execution time	Memory
497742		Ierus	Bigger segments (IZhO19_segments)	C++17	100 / 100	178 ms	29064 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
const int E = 5e5+777;
const long long inf = 1e18+777;
const int N = 3e3+777;
const int MOD = 1e9+7;
int n, a[E], t[E<<2], pref[E];
void update(int pos, int val, int v = 1, int tl = 0, int tr = n){
	if(tl == tr){
 		t[v] = val;
		return;
	}
	int mid = (tl + tr) / 2;
	if(pos <= mid){
		update(pos, val, v<<1, tl, mid);
	}else{
		update(pos, val, v<<1|1, mid + 1, tr);
	}
	t[v] = min(t[v<<1], t[v<<1|1]);
}
int get(int val, int v = 1, int tl = 0, int tr = n){
	if(tl == tr){
		return tl;
	}
	int mid = (tl + tr) / 2;
	if(t[v<<1|1] <= val){
		return get(val, v<<1|1, mid+1,tr);
	}else{
		return get(val, v<<1, tl, mid);
	}
}
pair<int,int> dp[E];
signed main(){
    ios_base::sync_with_stdio(0),
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
    	cin >> a[i];
    	pref[i] = pref[i-1] + a[i];
	}
	for(int i = 1; i <= n; ++i){
		update(i, LLONG_MAX);
	}
	update(0, 0);
	for(int i = 1; i <= n; ++i){
		int j = get(pref[i]);
		dp[i] = max(dp[i], {dp[j].first + 1, j});
		update(i,2 * pref[i] - pref[dp[i].second]);
	}
	cout << dp[n].first;
}

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