oj.uz

Submission #166774

# Submission time Handle Problem Language Result Execution time Memory
166774 2019-12-04T04:55:04 Z Trickster Divide and conquer (IZhO14_divide) C++14
17 / 100
 12 ms 1276 KB 
//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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 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 380 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 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1276 KB Output isn't correct
2 Halted 0 ms 0 KB -