Submission #1133866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133866		erentor353	Bigger segments (IZhO19_segments)	C++17	100 / 100	73 ms	15944 KiB

segments

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
template<typename T> using oset = 
__gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, 
__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T> void ckmin(T &x, T y){x = min(x, y);} 
template<typename T> void ckmax(T &x, T y){x = max(x, y);} 
#define vt vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ll long long
#define ull unsigned ll
#define ld long double
#define okey order_of_key
#define oget find_by_order
#define _gcf(x, y) __gcd(x, y)
#define _bits(x) __builtin_popcount(x)
#define MP make_pair
typedef vt<int> vi;
typedef pair<int,int> pi;
typedef pair<ll, ll> pll;
const ll MAXN = 5e5+1;
const ll MAXM = (1<<18)+1;
const ll MAXL = 30;
const ll MOD = 998244353;
const ll INF = INT64_MAX;
ll N, a[MAXN], pf[2*MAXN];
pll maxs[MAXN];
int bin(pll p, int idx){
	ll x = 2*pf[idx] - p.second;
	
	int lo = idx+1, hi = N;
	while(lo < hi){
		int mid = (hi - lo)/2 + lo;
		if(pf[mid] < x){
			lo = mid+1;
		}else{
			hi = mid;
		}
	}
	
	return hi;
}
void solve(){
	cin>>N;
	for(int i = 0; i<N; ++i){
		cin>>a[i];
	}
	
	pf[0] = a[0];
	pf[N+1] = INF;
	for(int i = 1; i<N; ++i){
		pf[i] = pf[i-1] + a[i];
	}
	
	for(int i = 0; i<N; ++i){
		maxs[i] = {1, 0};
	}
	
	for(int i = 0; i<N; ++i){
		int idx = bin(maxs[i], i);
		//cout<<i<<" "<<idx<<"\n";
		ckmax<pll>(maxs[idx], {maxs[i].first+1, pf[i]});
		if(i > 0) ckmax<pll>(maxs[i], maxs[i-1]);
		idx = bin(maxs[i], i);
		ckmax<pll>(maxs[idx], {maxs[i].first+1, pf[i]});
		
	}
	
	cout<<maxs[N-1].first<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin>>t;
	while(t--) solve();
}

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