Submission #1134723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134723		JelalTkm	Divide and conquer (IZhO14_divide)	C++20	100 / 100	40 ms	15688 KiB

divide

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e6 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

struct node {
  int x, g, d;
};

struct segtree {

  vector<pair<int, int>> tree, tree1;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, {INF, 0});
    tree1.assign(2 * size - 1, {-INF, 0});
  }
 
  void build(vector<int> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size() && lx) {
        tree[x].first = a[lx];
        tree[x].second = lx;
        tree1[x].first = a[lx];
        tree1[x].second = lx;
      }
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      if (tree[2 * x + 1].first <= tree[2 * x + 2].first)
        tree[x] = tree[2 * x + 1];
      else tree[x] = tree[2 * x + 2];

      if (tree1[2 * x + 1].first >= tree1[2 * x + 2].first)
        tree1[x] = tree1[2 * x + 1];
      else tree1[x] = tree1[2 * x + 2];
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size());
    build(a, 0, 0, size);
  }

  pair<int, int> get(int l, int r, int y, int x, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return {INF, -1};
    }
    if (lx >= l && rx <= r) {
      return tree[x];
    }
    int m = (lx + rx) >> 1;
    auto s1 = get(l, r, y, 2 * x + 1, lx, m);
    auto s2 = get(l, r, y, 2 * x + 2, m, rx);
    if ((y - s1.first) >= 0)
      return s1;
    else return s2;
  }

  pair<int, int> get(int r, int y) {
    auto pr = get(1, r, y, 0, 0, size);
    return pr;
  }

};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<node> a(n + 1);
    for (int i = 1; i <= n; i++)
      cin >> a[i].x >> a[i].g >> a[i].d;

    vector<int> pref_d(n + 1), pref_g(n + 1), prefd(n + 1);
    vector<pair<int, int>> all(n);
    for (int i = 1; i <= n; i++) {
      pref_d[i] = pref_d[i - 1] + a[i].d;
      pref_g[i] = pref_g[i - 1] + a[i].g;
      prefd[i] = pref_d[i - 1] - a[i].x;
      all[i - 1] = make_pair(prefd[i], i);
    }

    sort(all.begin(), all.end());
    // for (int i = 0; i < n; i++)
    //   cout << all[i].first << " " << all[i].second << '\n';
    // cout << '\n';
    vector<int> mn(n);
    mn[0] = all[0].second;
    for (int i = 1; i < n; i++)
      mn[i] = min(mn[i - 1], all[i].second);

    segtree st;
    st.build(prefd);

    int ans = pref_g[1];
    for (int i = 2; i <= n; i++) {
      int y = pref_d[i] - a[i].x;
      auto x = st.get(i, y);
      auto l = upper_bound(all.begin(), all.end(), make_pair(y, 0), 
       [](const pair<int, int>& a, const pair<int, int>& b) {
       return a.first < b.first;
      }) - all.begin();
      l--;
      // cout << y << " " << l << '\n';
      if (l >= 0)
        ans = max(ans, pref_g[i] - pref_g[mn[l] - 1]);
      // if (y - x.first >= 0)
      //   ans = max(ans, pref_g[i] - pref_g[x.second - 1]);
      ans = max(ans, pref_g[i] - pref_g[i - 1]);
    }

    cout << ans << '\n';
  }

  return 0;
}

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