Submission #166774

#	Time	Username	Problem	Language	Result	Execution time	Memory
166774		Trickster	Divide and conquer (IZhO14_divide)	C++14	17 / 100	12 ms	1276 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];
		
		M[P[i] - E[i]] = 1;
		M[P[i] - E[i-1]] = 1;
	}
	
	ll now = 0, cur = 0;
	for(auto &i: M) i.ss = ++now;
	
	for(ll i = 1; i <= n; i++) {
		ll ans = tap(M[P[i]-E[i]], 1, now, 1) + G[i];
		
		cur = max(cur, ans);
		
//		cout << ans << " " << M[P[i]-E[i]] << " " << M[P[i]-E[i]] << "\n";
		
		upd(M[P[i]-E[i-1]], ans, 1, now, 1);
	}
	cout << cur;
}

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