oj.uz

Submission #169129

# Submission time Handle Problem Language Result Execution time Memory
169129 2019-12-18T13:56:35 Z LinusTorvaldsFan Divide and conquer (IZhO14_divide) C++14
100 / 100
 344 ms 149084 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 100000 + 7;

typedef long long ll;

const ll infll = 1e15;

int x[maxn];
int g[maxn];
int d[maxn];
ll pr_d[maxn];
ll pr_g[maxn];

struct Node {
	ll l, r;
	ll val;
	Node* left;
	Node* right;
	Node(ll val_, ll l_, ll r_) {
		val = val_;
		l = l_;
		r = r_;
		left = nullptr;
		right = nullptr;
	}
};

void pull(Node* root) {
	if (root->left != nullptr) {
		root->val = min(root->val, root->left->val);
	}
	if (root->right != nullptr) {
		root->val = min(root->val, root->right->val);
	}
}

void add(Node* root, ll val, ll ind) {
	if (root->l == ind && root->r == ind + 1) {
		root->val = min(val,root->val);
		return;
	}
	ll m = (root->l + root->r) / 2;
	if (ind < m) {
		if (root->left == nullptr) {
			root->left = new Node(val, root->l, m);
		}
		add(root->left, val, ind);
	}
	else {
		if (root->right == nullptr) {
			root->right = new Node(val, m, root->r);
		}
		add(root->right, val, ind);
	}
	pull(root);
}

ll get(Node* root, ll l, ll r) {
	if (root->l >= r || root->r <= l) {
		return infll;
	}
	if (root->l >= l && root->r <= r) {
		return root->val;
	}
	ll ans = infll;
	if (root->left != nullptr) {
		ans = min(ans, get(root->left, l, r));
	}
	if (root->right != nullptr) {
		ans = min(ans, get(root->right, l, r));
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> g[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		pr_d[i] = (i>0?pr_d[i-1]:0) + d[i];
		pr_g[i] = (i > 0 ? pr_g[i - 1] : 0) + g[i];
	}
	Node* root = new Node(infll, -infll, infll);
	ll gold = 0;
	for (int i = 0; i < n; i++) {
		ll  val = (i > 0 ? pr_g[i - 1] : 0);
		ll ind = (i > 0 ? pr_d[i - 1] : 0) - x[i];
		add(root, val, ind);
		ll cur = pr_d[i] - x[i];
		gold = max(gold, pr_g[i] - get(root, -infll, cur+1));
	}
	cout << gold;
	return 0;
}

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 380 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 504 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 504 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 3 ms 892 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 4 ms 1272 KB Output is correct
6 Correct 6 ms 2168 KB Output is correct
7 Correct 4 ms 1400 KB Output is correct
8 Correct 4 ms 1400 KB Output is correct
9 Correct 4 ms 892 KB Output is correct
10 Correct 6 ms 1400 KB Output is correct
11 Correct 15 ms 4856 KB Output is correct
12 Correct 16 ms 5112 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2680 KB Output is correct
2 Correct 21 ms 5508 KB Output is correct
3 Correct 27 ms 10080 KB Output is correct
4 Correct 134 ms 49532 KB Output is correct
5 Correct 136 ms 49564 KB Output is correct
6 Correct 344 ms 149084 KB Output is correct
7 Correct 281 ms 101004 KB Output is correct
8 Correct 264 ms 101112 KB Output is correct
9 Correct 195 ms 51576 KB Output is correct
10 Correct 164 ms 34252 KB Output is correct
11 Correct 241 ms 73036 KB Output is correct
12 Correct 231 ms 72056 KB Output is correct