Submission #1134682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134682		JelalTkm	Divide and conquer (IZhO14_divide)	C++20	0 / 100	1 ms	320 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 {

  struct node2 {
    int pref_d, suff_d, pref_g, suff_g, seg_d, seg_g, pref_ind, suff_ind, sum_d, sum_g, sum_ind, start;
  };
  vector<node2> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
  }
 
  void build(vector<node> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size()) {
        tree[x].pref_d = tree[x].suff_d = tree[x].seg_d = a[lx].d;
        tree[x].pref_g = tree[x].suff_g = tree[x].seg_g = a[lx].g;
        tree[x].pref_ind = tree[x].suff_ind = a[lx].x;
        tree[x].sum_d = a[lx].d;
        tree[x].sum_g = a[lx].g;
        tree[x].sum_ind = a[lx].x;
        tree[x].start = a[lx].x;
      }
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x].pref_d = tree[2 * x + 1].pref_d;
      tree[x].pref_g = tree[2 * x + 1].pref_g;
      tree[x].pref_ind = tree[2 * x + 1].pref_ind;
      if (tree[2 * x + 2].pref_ind - tree[2 * x + 1].start <= tree[2 * x + 1].sum_d + tree[2 * x + 2].pref_d) {
        tree[x].pref_d = tree[2 * x + 1].sum_d + tree[2 * x + 2].pref_d;
        if (tree[2 * x + 2].pref_d)
          tree[x].pref_ind = tree[2 * x + 2].pref_ind;
        else tree[x].pref_ind = tree[2 * x + 1].pref_ind;
        tree[x].pref_g = tree[2 * x + 1].sum_g + tree[2 * x + 2].pref_g;
      }

      tree[x].suff_d = tree[2 * x + 2].suff_d;
      tree[x].suff_g = tree[2 * x + 2].suff_g;
      if (tree[2 * x + 2].suff_g)
        tree[x].suff_ind = tree[2 * x + 2].suff_ind;
      else tree[x].suff_ind = tree[2 * x + 1].suff_ind;
      if (tree[2 * x + 2].sum_ind - tree[2 * x + 1].suff_ind <= tree[2 * x + 2].sum_d + tree[2 * x + 1].suff_d) {
        tree[x].suff_d = tree[2 * x + 2].sum_d + tree[2 * x + 1].suff_d;
        tree[x].suff_ind = tree[2 * x + 1].suff_ind;
        tree[x].suff_g = tree[2 * x + 2].sum_g + tree[2 * x + 1].suff_g;
      }

      tree[x].sum_d = tree[2 * x + 1].sum_d + tree[2 * x + 2].sum_d;
      tree[x].sum_g = tree[2 * x + 1].sum_g + tree[2 * x + 2].sum_g;
      tree[x].start = tree[2 * x + 1].start;
      if (tree[2 * x + 2].sum_d)
        tree[x].sum_ind = tree[2 * x + 2].sum_ind;
      else tree[x].sum_ind = tree[2 * x + 1].sum_ind;
      tree[x].seg_d = max({tree[2 * x + 1].seg_d, tree[2 * x + 2].seg_d, tree[x].pref_d, tree[x].suff_d});
      tree[x].seg_g = max({tree[2 * x + 1].seg_g, tree[2 * x + 2].seg_g, tree[x].pref_g, tree[x].suff_g});
    }
  }
 
  void build(vector<node> &a) {
    init((int) a.size());
    build(a, 0, 0, size);
  }

  int get() {
    return tree[0].seg_g;
  }
 
  // void set(int i, int v, int x, int lx, int rx) {
  //   if (rx - lx == 1) {
  //     tree[x] = v;
  //     return;
  //   }
  //   int m = (lx + rx) >> 1;
  //   if (i < m) {
  //     set(i, v, 2 * x + 1, lx, m);
  //   } else {
  //     set(i, v, 2 * x + 2, m, rx);
  //   }
  //   tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  // }
 
  // void set(int i, int v) {
  //   set(i, v, 0, 0, size);
  // }
 
  // int sum(int l, int r, int x, int lx, int rx) {
  //   if (l >= rx || lx >= r) {
  //     return 0;
  //   }
  //   if (lx >= l && rx <= r) {
  //     return tree[x];
  //   }
  //   int m = (lx + rx) >> 1;
  //   int s1 = sum(l, r, 2 * x + 1, lx, m);
  //   int s2 = sum(l, r, 2 * x + 2, m, rx);
  //   return s1 + s2;
  // }
 
  // int sum(int l, int r) {
  //   return sum(l, r, 0, 0, size);
  // }
};

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);
    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;
    }

    int ans = 0;
    for (int i = 2; i <= n; i++) {
      int y = prefd[i] + a[i].d;
      int l = 0, r = i;
      while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (y - prefd[mid] >= 0)
          r = mid;
        else l = mid;
      }
      ans = max(ans, pref_g[i] - pref_g[r - 1]);
    }

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

  return 0;
}
// (pref[y] - y) - (pref[x - 1] - x) >= 0

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