Submission #5015

#	Time	Username	Problem	Language	Result	Execution time	Memory
5015		tncks0121	Divide and conquer (IZhO14_divide)	C++98	100 / 100	104 ms	7188 KiB

divide

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005, LEAF = 1<<17;

int N, X[N_], G[N_], D[N_];
ll SG[N_], SD[N_];
ll res;

int O[N_], W[N_];
ll V[N_];
bool cmpO(const int &a, const int &b) { return V[a] < V[b]; }

ll Tree[N_+LEAF];

void update (int x, ll v) {
	Tree[x += LEAF] = v;
	while(x >>= 1) Tree[x] = max(Tree[x+x], Tree[x+x+1]);
}

ll get (int x, int y) {
	ll ret = 0;
	x += LEAF; y += LEAF;
	while(x <= y) {
		if((x & 1) == 1) ret = max(ret, Tree[x]);
		if((y & 1) == 0) ret = max(ret, Tree[y]);
		x = (x+1)>>1;
		y = (y-1)>>1;
	}
	return ret;
}

int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d%d%d", X+i, G+i, D+i);
	for(int i = 1; i <= N; i++) SG[i] = SG[i-1]+G[i], SD[i] = SD[i-1]+D[i], V[i] = SD[i]-X[i];
	for(int i = 1; i <= N; i++) O[i] = i;
	sort(O+1, O+N+1, cmpO);

	for(int i = 1; i <= N; i++) update(i, SG[O[i]]), W[O[i]] = i;
	for(int i = 1; i <= N; i++) {
		int low = 1, high = N, p = -1;
		while(low <= high) {
			int mid = (low + high) >> 1;
			if(SD[i-1]-X[i] <= V[O[mid]]) {
				p = mid;
				high = mid - 1;
			}else {
				low = mid + 1;
			}
		}

		res = max(res, get(p,N) - SG[i-1]);
		update(W[i], 0);
	}

	printf("%lld\n", res);

	return 0;
}

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