oj.uz

Submission #5015

# Submission time Handle Problem Language Result Execution time Memory
5015 2014-01-27T15:08:26 Z tncks0121 Divide and conquer (IZhO14_divide) C++
100 / 100
 104 ms 7188 KB 
#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.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7188 KB Output is correct
2 Correct 4 ms 7188 KB Output is correct
3 Correct 4 ms 7188 KB Output is correct
4 Correct 40 ms 7188 KB Output is correct
5 Correct 40 ms 7188 KB Output is correct
6 Correct 84 ms 7188 KB Output is correct
7 Correct 68 ms 7188 KB Output is correct
8 Correct 64 ms 7188 KB Output is correct
9 Correct 68 ms 7188 KB Output is correct
10 Correct 76 ms 7188 KB Output is correct
11 Correct 96 ms 7188 KB Output is correct
12 Correct 104 ms 7188 KB Output is correct