Submission #166775

#	Time	Username	Problem	Language	Result	Execution time	Memory
166775		Trickster	Divide and conquer (IZhO14_divide)	C++14	100 / 100	381 ms	22256 KiB

divide

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define N 1000010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <ll, ll>

using namespace std;

ll n;
ll T[N*4];
map <ll, ll> M;
ll E[N], P[N], G[N];

ll tap(ll pos, ll l, ll r, ll node)
{
	if(r < pos) return 0;
	
	if(l >= pos) return T[node];
	
	return max(tap(pos, l, (l+r)/2, node*2), tap(pos, (l+r)/2+1, r, node*2+1));
}
void upd(ll pos, ll x, ll l, ll r, ll node)
{
	if(l == r) {
		T[node] = max(x, T[node]);
		return;
	}
	
	if(pos <= (l+r)/2)
		upd(pos, x, l, (l+r)/2, node*2);
	else
		upd(pos, x, (l+r)/2+1, r, node*2+1);
	
	T[node] = max(T[node*2], T[node*2+1]);
}

int main()
{
	cin >> n;
	
	for(ll i = 1; i <= n; i++) {
		cin >> P[i] >> G[i] >> E[i];
		
		E[i] += E[i-1];
		G[i] += G[i-1];
		
		M[E[i] - P[i]] = 1;
		M[E[i-1] - P[i]] = 1;
	}
	
	ll now = 0, cur = 0;
	for(auto &i: M) i.ss = ++now;
	
	for(ll i = n; i >= 1; i--) {
		upd(M[E[i] - P[i]], G[i], 1, now, 1);
		
		cur = max(tap(M[E[i-1] - P[i]], 1, now, 1) - G[i-1], cur);
	}
	cout << cur;
}

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