Submission #953679

#	Time	Username	Problem	Language	Result	Execution time	Memory
953679		esomer	Bigger segments (IZhO19_segments)	C++17	100 / 100	204 ms	29624 KiB

segments

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

struct segTree {
	vector<long long> v, upd;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		v.assign(2 * sz, 1e18);
		upd.assign(2 * sz, 0);
	}
	void set(int l, int r, long long val, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			if(v[x] == 1e18) v[x] = 0;
			v[x] += val;
			upd[x] += val;
			// cout << "lx " << lx << " rx " << rx << 
			return;
		}else if(lx >= r || rx <= l) return;
		int m = (lx + rx) / 2;
		set(l, r, val, 2 * x + 1, lx, m);
		set(l, r, val, 2 * x + 2, m, rx);
		v[x] = min(v[2 * x + 1], v[2 * x + 2]) + upd[x];
	}

	void set(int l, int r, long long val){
		set(l, r, val, 0, 0, sz);
	}

	int walk(int x, int lx, int rx, long long curr){
		if(rx - lx == 1){
			return lx;
		}
		int m = (lx + rx) / 2;
		curr += upd[x];
		if(v[2 * x + 2] + curr <= 0) return walk(2 * x + 2, m, rx, curr);
		else return walk(2 * x + 1, lx, m, curr);
	}

	int walk(){
		return walk(0, 0, sz, 0);
	}
};

long long sum(int l, int r, vector<long long>& prefix){
	if(l > r) return 0;
	return prefix[r] - prefix[l-1];
}

int solve(int N, vector<int>& a){
	vector<long long> prefix(N+1, 0);
	for(int i = 1; i <= N; i++){
		prefix[i] = prefix[i-1] + a[i];
	}
	vector<int> ans(N+1);
	ans[0] = 0;
	segTree st; st.init(N+1);
	st.set(0, 1, 0);
	for(int i = 1; i <= N; i++){
		st.set(0, i, -a[i]);
		int ind = st.walk();
		ans[i] = ans[ind] + 1;
		long long sm = sum(ind + 1, i, prefix);
		// cout << "i " << i << " ind " << ind << " sm " << sm << "\n";
		st.set(i, i + 1, sm);
	}
	return ans[N];
}

int brute(int N, vector<int>& a){
	int ans = 0;
	for(int b = 0; b < (1 << N); b++){
		long long lst = 0;
		long long sm = 0;
		bool gd = true;
		int segments = 0;
		// cout << "b " << b << "\n";
		for(int i = 0; i < N; i++){
			sm += a[i+1];
			if((1 << i) & b || i == N - 1){
				// cout << "i " << 
				segments++;
				if(lst > sm) gd = false;
				lst = sm;
				sm = 0;
			}
		}
		if(gd) ans = max(ans, segments);
	}
	return ans;
}

mt19937 gen(time(0));

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

	// string s; cin >> s;
	string s = "RUN";
	if(s == "RUN"){
		int N; cin >> N;
		vector<int> a(N+1, 0);
		for(int i = 1; i <= N; i++) cin >> a[i];
		cout << solve(N, a) << "\n";
		return 0;
	}
	for(int h = 0; h < 1000000; h++){
		int n = gen() % 10;
		vector<int> a(n+1, 0);
		for(int i = 0; i < n; i++){
			a[i] = gen() % 10 + 1;
		}
		int ans1 = solve(n, a);
		int ans2 = brute(n, a);
		if(ans1 != ans2){
			cout << n << "\n";
			for(int i = 1; i <= n; i++) cout << a[i] << " ";
			cout << "\n";
			cout << "Fast ans: " << ans1 << "\n";
			cout << "Slow ans: " << ans2 << "\n";
			return 0;
		}
	}
}

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