Submission #161233

#	Time	Username	Problem	Language	Result	Execution time	Memory
161233		MohamedAhmed04	Divide and conquer (IZhO14_divide)	C++14	100 / 100	98 ms	9308 KiB

divide

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

long long a[MAX] , e[MAX] , v[MAX] , pref[MAX] , prefv[MAX] ;
long long tree[4 * MAX] ;
long long sum = 0ll ;

void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[node] = pref[l] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid + 1 , r) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}

void update(int node , int l , int r , int idx)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node] = -1e12 ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx) ;
	update(node << 1 | 1 , mid + 1 , r , idx) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}

int query(int node , int l , int r)
{
	if(l == r)
		return l ;
	int mid = (l + r) >> 1 ;
	if(tree[node << 1 | 1]+sum >= 0)
		return query(node << 1 | 1 , mid+1 , r) ;
	else
		return query(node << 1 , l , mid) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	int n ;
	cin>>n ;
	long long a[n] , e[n] , v[n] ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>a[i]>>v[i]>>e[i] ;
	e[0] = 0 , v[0] = 0 , a[0] = a[1] ;
	for(int i = 1 ; i <= n ; ++i)
	{
		pref[i] = pref[i-1] - (a[i] - a[i-1]) + e[i] ;
		prefv[i] = prefv[i-1] + v[i] ;
	}
	build(1 , 1 , n) ;
	long long ans = 0ll ;
	for(int i = 1 ; i <= n ; ++i)
	{
		sum += a[i] - a[i-1] - e[i-1] ;
		int idx = query(1 , 1 , n) ;
		ans = max(ans , prefv[idx] - prefv[i-1]) ;
		update(1 , 1 , n , i) ;
	}
	return cout<<ans<<"\n" ,  0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52