Submission #255260

#	Time	Username	Problem	Language	Result	Execution time	Memory
255260		tuna	Divide and conquer (IZhO14_divide)	C++11	100 / 100	852 ms	100784 KiB

divide

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5, M = 2e14;

int n;
ll x[N], g[N], d[N];

map<ll, ll> tree;

void upd(ll k, ll x) {
  while (k < M) {
    if (tree.find(k) == tree.end()) {
      tree[k] = x;
    } else {
      tree[k] = min(tree[k], x);
    }
    k += k & -k;
  }
}

ll que(ll k) {
  ll ans = LLONG_MAX;
  while (k) {
    if (tree.find(k) != tree.end()) {
      ans = min(ans, tree[k]);
    }
    k -= k & -k;
  }
  return ans;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> g[i] >> d[i];
    d[i] += d[i - 1];
    g[i] += g[i - 1];
  }
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    upd(d[i - 1] - x[i] + M / 2, g[i - 1]);
    ans = max(ans, g[i] - que(d[i] - x[i] + M / 2));
  }
  cout << ans;
}

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