Submission #863509

#	Time	Username	Problem	Language	Result	Execution time	Memory
863509		letterc67	Bigger segments (IZhO19_segments)	C++14	100 / 100	113 ms	36448 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
const ll nmax = 5e5+6;
const ll inf = 1e18;
ll a[nmax];
ll pref[nmax];
ll n;
struct segtre{
	ll st[nmax * 4];
	void init(int n){
		for(int i = 1;i<=4*n;i++) st[i] = inf;
	}
	void update(int id,int l,int r,int i,ll x){
		if(i>r ||i <l) return;
		if(l==r) {
			st[id] = x;
			return;
		}
		int mid = (l+r)/2;
		update(id*2,l,mid,i,x);
		update(id*2+1,mid+1,r,i,x);
		st[id] = min(st[id*2],st[id*2+1]);
	}
	ll walk(int id,int l,int r,ll x){
		if (l==r) return l ;
		int mid = (l+r)/2;
		if(st[id*2] <= x) return walk(id*2,l,mid,x);
		return walk(id*2+1,mid+1,r,x);
	}
} tree;
ll dp[nmax];
ll f[nmax];
void solve(){
    cin >> n;
    for(int i = 1;i<=n;i++){
    	cin >> a[i];
    	// pref[i] = pref[i-1] + a[i];
    }
  reverse(a + 1, a + n + 1);
    tree.init(n+1);
    tree.update(1,1,n+1,n+1,0);
    for(int i = n;i>=1;i--){
    	pref[i] = pref[i+1] + a[i];
    	int get = tree.walk(1,1,n+1,pref[i]);
    	// cout << get << '\n';
    	f[i] = pref[i] - pref[get];
    	dp[i] = dp[get] + 1;
    	tree.update(1,1,n+1,i,f[i] + pref[i]);
    }
    // cout << f[2];
    cout << dp[1];
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}

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