Submission #1134695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134695		JelalTkm	Divide and conquer (IZhO14_divide)	C++20	17 / 100	1 ms	328 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;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.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;
      }
    } 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];
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size());
    build(a, 0, 0, size);
  }

  pair<int, int> get(int l, int r, 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, 2 * x + 1, lx, m);
    auto s2 = get(l, r, 2 * x + 2, m, rx);
    if (s1.first <= s2.first)
      return s1;
    else return s2;
  }

  pair<int, int> get(int r) {
    auto pr = get(1, r, 0, 0, size);
    return pr;
  }
 
  // 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;
    }

    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);
      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: 0 / 31
• Subtask 3: 0 / 52