Submission #1172034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172034		coolboy19521	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	328 KiB

segments

#include "bits/stdc++.h"

#define mxN 500005

using namespace std;

struct stree{
	pair<int,int> ar[4 * mxN];

	void upd(int i, pair<int,int> x, int l, int r, int v){
		if (l < r) {
			int mi = (l + r) / 2;
			
			if (i <= mi)
				upd(i, x, l, mi, v * 2);
			else
				upd(i, x, mi + 1, r, v * 2 + 1);
			
			ar[v] = max(ar[v * 2], ar[v * 2 + 1]);
		} else ar[v] = x;
	}
	
	pair<int,int> qry(int a, int b, int l, int r, int v){
		if (a <= l && b <= r)
			return ar[v];
		else if (a <= r && l <= b){
			int mi = (l + r) / 2;
			
			pair<int,int> lr = qry(a, b, l, mi, v * 2);
			pair<int,int> rr = qry(a, b, mi + 1, r, v * 2 + 1);
			
			return max(lr, rr);
		}
		else return {0, 0};
	}
} st;

int bf[mxN], tb[mxN], pr[mxN];
int a[mxN];

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

	map<int,int> mp;
	
	for (int i = 1; i <= N; i ++){
		bf[i] = mp[a[i]];
		mp[a[i]] = i;
	}

	priority_queue<tuple<int,int,int>> pq;
	
	int aux = 0, ans = 0;
	
	for (int i = 1; i <= N; i ++){
		pr[i] = aux += a[i];

		for(;;){
			if (pq.empty()) break;
			auto [sm, cn, ix] = pq.top();
			
			sm = -sm;
			
			if (sm - aux <= 0){
				st.upd(ix, {cn, ix}, 1, N, 1);
				pq.pop();
			}
			
			else break;
		}
		
		auto [cn, ix] = st.qry(bf[i] + 1, i, 1, N, 1);
		ans = cn + 1;
		
		pq.emplace(pr[ix] - pr[i] - aux, cn + 1, i);
	}
	
	cout << ans << endl;
}

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