Submission #131130

#	Time	Username	Problem	Language	Result	Execution time	Memory
131130		maruii	Divide and conquer (IZhO14_divide)	C++14	100 / 100	72 ms	6864 KiB

divide

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int SIZE = 1 << 17;
struct ST {
	int V[2 * SIZE];
	void update(int x, int v) {
		for (x += SIZE; x; x >>= 1) V[x] = max(V[x], v);
	}
	int query(int s, int e) {
		int ret = 0;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, V[s++]);
			if (~e & 1) ret = max(ret, V[e--]);
		}
		return ret;
	}
} seg;

int X[100005];
ll G[100005], D[100005];
vector<ll> xx;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i] >> G[i] >> D[i];
		G[i] += G[i - 1];
		D[i] += D[i - 1];
		xx.push_back(D[i] - X[i]);
	}
	sort(xx.begin(), xx.end()); xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) seg.update(lower_bound(xx.begin(), xx.end(), D[i] - X[i]) - xx.begin(), i);
	ll ans = 0;
	for (int i = 1; i <= N; ++i) ans = max(ans, G[seg.query(lower_bound(xx.begin(), xx.end(), D[i - 1] - X[i]) - xx.begin(), xx.size())] - G[i - 1]);
	cout << ans;
	return 0;
}

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