Submission #1134703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134703		JelalTkm	Divide and conquer (IZhO14_divide)	C++20	0 / 100	0 ms	324 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<int> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, INF);
  }
 
  void build(vector<int> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size() && lx) {
        tree[x] = a[lx];
      }
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size());
    build(a, 0, 0, size);
  }

  int get(int l, int r, int x, int lx, int rx) {
    if (rx - lx == 1) {
      return tree[x];
    }
    int m = (lx + rx) >> 1;
    int s1;
    if (m - lx == 1 && lx)
      s1 = get(l, r, 2 * x + 1, lx, m);
    if (m < r && tree[2 * x + 1] > tree[2 * x + 2])
      s1 = get(l, r, 2 * x + 2, m, rx);
    return s1;
  }

  int get(int r) {
    return get(1, r, 0, 0, size);
  }

};

bool cmp(node &t1, node &t2) {
  return t1.x < t2.x;
}

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;

    sort(a.begin(), a.end(), cmp);

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

    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;
      int x = st.get(i);
      if (y - prefd[x] >= 0)
        ans = max(ans, pref_g[i] - pref_g[x - 1]);
      ans = max(ans, pref_g[i] - pref_g[i - 1]);
    }

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

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

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