oj.uz

Submission #161233

# Submission time Handle Problem Language Result Execution time Memory
161233 2019-11-01T14:19:05 Z MohamedAhmed04 Divide and conquer (IZhO14_divide) C++14
100 / 100
 98 ms 9308 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 7 ms 1144 KB Output is correct
3 Correct 8 ms 1144 KB Output is correct
4 Correct 32 ms 4088 KB Output is correct
5 Correct 36 ms 4856 KB Output is correct
6 Correct 74 ms 9308 KB Output is correct
7 Correct 61 ms 8056 KB Output is correct
8 Correct 98 ms 8184 KB Output is correct
9 Correct 61 ms 7928 KB Output is correct
10 Correct 63 ms 7980 KB Output is correct
11 Correct 68 ms 8440 KB Output is correct
12 Correct 75 ms 8600 KB Output is correct