oj.uz

Submission #36392

# Submission time Handle Problem Language Result Execution time Memory
36392 2017-12-08T15:10:49 Z cheater2k Divide and conquer (IZhO14_divide) C++14
100 / 100
 69 ms 11536 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const long long inf = 1e18;

int n;
long long x[N], g[N], d[N];
long long T[N];
long long ans;
vector<long long> z; // for compression

void upd(int x, long long val) { for(; x < N; x += x & -x) T[x] = min(T[x], val); }
long long get(int x) { long long res = inf; for (; x > 0; x -= x & -x) res = min(res, T[x]); return res; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> g[i] >> d[i]; // (coordinate, gold, energy)
		d[i] += d[i-1];
		g[i] += g[i-1];
	}
	for (int i = 1; i <= n; ++i) {
		// compress all values
		z.push_back(d[i] - x[i]);
		z.push_back(d[i-1] - x[i]);
	}
	sort(z.begin(), z.end());
	z.resize(distance(z.begin(), unique(z.begin(), z.end())));

	for (int i = 0; i < N; ++i) T[i] = inf;
	for (int i = 1; i <= n; ++i) {
		int pos = lower_bound(z.begin(), z.end(), d[i-1] - x[i]) - z.begin() + 1;
		upd(pos, g[i-1]); // update to BIT

		pos = lower_bound(z.begin(), z.end(), d[i] - x[i]) - z.begin() + 1;
		long long cur = g[i] - get(pos);
		ans = max(ans, cur); // update to answer
	}

	cout << ans << endl;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8584 KB Output is correct
2 Correct 6 ms 8844 KB Output is correct
3 Correct 6 ms 8844 KB Output is correct
4 Correct 26 ms 10000 KB Output is correct
5 Correct 36 ms 10000 KB Output is correct
6 Correct 56 ms 11536 KB Output is correct
7 Correct 49 ms 11536 KB Output is correct
8 Correct 59 ms 11536 KB Output is correct
9 Correct 69 ms 11536 KB Output is correct
10 Correct 59 ms 11536 KB Output is correct
11 Correct 63 ms 11536 KB Output is correct
12 Correct 53 ms 11536 KB Output is correct