Submission #213177

#	Time	Username	Problem	Language	Result	Execution time	Memory
213177		islingr	Divide and conquer (IZhO14_divide)	C++14	100 / 100	63 ms	6648 KiB

divide

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define ff first
#define ss second

using ll = int64_t;

template<class T> bool ckmin(T &a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1 << 17;
const int inf = 1e9;
int t[N << 1];

int n;
int query(int l, int r) {
	int res = inf;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) ckmin(res, t[l++]);
		if (r & 1) ckmin(res, t[--r]);
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	vector<ll> x(n), g(n + 1), e(n + 1), diff(n);
	rep(i, 0, n) {
		cin >> x[i] >> g[i + 1] >> e[i + 1];
		g[i + 1] += g[i];
		e[i + 1] += e[i];
		diff[i] = x[i] - e[i];
	}
	rep(i, 0, n) t[i + n] = i;
	sort(t + n, t + 2 * n, [&](int a, int b) { return diff[a] < diff[b]; });
	for (int i = n - 1; i; --i) t[i] = min(t[i << 1|0], t[i << 1|1]);
	sort(all(diff));

	ll ans = 0;
	rep(i, 0, n) {
		// Find smallest j such that x[j] - e[j] >= x[i] - e[i + 1] 
		int k = lb(all(diff), x[i] - e[i + 1]) - begin(diff);
		// [k, n) are the elements such that diff[k] >= x[i] - e[i + 1]
		// find smallest j in [k, n) in segtree 
		int j = query(k, n);
		ckmax(ans, g[i + 1] - g[j]);
	}
	cout << ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52