Submission #134723

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134723	2019-07-23T07:59:00 Z	someone_aa	Divide and conquer (IZhO14_divide)	C++17	100 / 100	360 ms	73976 KB

divide

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll gold[maxn], energy[maxn], x[maxn], n;
ll prefix_g[maxn], prefix_e[maxn];

class node {
public:
	ll lb, rb;
	ll value;
	node *lchild, *rchild;

	node(ll _lb, ll _rb) {
		lb = _lb;
		rb = _rb;
		value = LLONG_MAX;
		lchild = rchild = NULL;
	}
	ll get_val(node *x) {
		if(x == NULL) return LLONG_MAX;
		else return x->value;
	}
	void update(ll x, ll val) {
		if(lb == rb) {
			value = min(value, val);
		}
		else {
			ll mid = lb + (rb - lb) / 2;

			if(x <= mid) {
				if(lchild == NULL) lchild = new node(lb, mid);
				lchild -> update(x, val);
			}
			else {
				if(rchild == NULL) rchild = new node(mid+1, rb);
				rchild -> update(x, val);
			}
			
			value = min(get_val(lchild), get_val(rchild));
		}
	}
	ll query(ll ql, ll qr) {
		if(lb > qr || rb < ql) return LLONG_MAX;
		else if(lb >= ql && rb <= qr) return value;
		else {
			ll mid = lb + (rb - lb) / 2;

			ll l_val = LLONG_MAX;
			if(lchild != NULL) l_val = lchild -> query(ql, qr);

			ll r_val = LLONG_MAX;
			if(rchild != NULL) r_val = rchild -> query(ql, qr);

			return min(l_val, r_val);
		}
	}
};

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>x[i]>>gold[i]>>energy[i];

		prefix_g[i] = prefix_g[i-1] + gold[i];
		prefix_e[i] = prefix_e[i-1] + energy[i];
	}

	node *root = new node(1LL*INT_MIN, 1LL*INT_MAX);

	ll result = 0LL;
	for(int i=1;i<=n;i++) {

		root->update(x[i] - prefix_e[i-1], prefix_g[i-1]);	
		result = max(result, prefix_g[i] - root->query(x[i] - prefix_e[i], INT_MAX));
	}
	cout<<result<<"\n";
}

Compilation message

divide.cpp: In member function 'long long int node::query(long long int, long long int)':
divide.cpp:49:7: warning: unused variable 'mid' [-Wunused-variable]
    ll mid = lb + (rb - lb) / 2;
       ^~~

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	376 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	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	4 ms	888 KB	Output is correct
4	Correct	4 ms	1016 KB	Output is correct
5	Correct	5 ms	1144 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	1272 KB	Output is correct
8	Correct	5 ms	1272 KB	Output is correct
9	Correct	6 ms	888 KB	Output is correct
10	Correct	7 ms	1272 KB	Output is correct
11	Correct	21 ms	4904 KB	Output is correct
12	Correct	21 ms	5112 KB	Output is correct

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2680 KB	Output is correct
2	Correct	26 ms	5628 KB	Output is correct
3	Correct	29 ms	5632 KB	Output is correct
4	Correct	104 ms	6684 KB	Output is correct
5	Correct	121 ms	7900 KB	Output is correct
6	Correct	261 ms	7132 KB	Output is correct
7	Correct	180 ms	10104 KB	Output is correct
8	Correct	193 ms	10336 KB	Output is correct
9	Correct	265 ms	52472 KB	Output is correct
10	Correct	258 ms	35236 KB	Output is correct
11	Correct	360 ms	73976 KB	Output is correct
12	Correct	340 ms	73132 KB	Output is correct