Submission #134723

#	Time	Username	Problem	Language	Result	Execution time	Memory
134723		someone_aa	Divide and conquer (IZhO14_divide)	C++17	100 / 100	360 ms	73976 KiB

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 (stderr)

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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52