Submission #863155

#	Time	Username	Problem	Language	Result	Execution time	Memory
863155		truongdoan2012	Bigger segments (IZhO19_segments)	C++17	100 / 100	192 ms	23524 KiB

segments

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;
const int N = 5e5 + 10;
i64 t[N << 2];

void upd(int id, int l, int r, int p, i64 v) {
  if (l == r) {
    return void(t[id] = v);
  }
  int mid = (l + r) >> 1;
  if (p <= mid) {
    upd(id << 1, l, mid, p, v);
  } else {
    upd(id << 1 | 1, mid + 1, r, p, v);
  }
  t[id] = min(t[id << 1], t[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v, i64 val) {
  if (l > v || r < u || t[id] > val) {
    return -1;
  }
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1;
  auto rs = get(id << 1 | 1, mid + 1, r, u, v, val);
  if (~rs) {
    return rs;
  }
  return get(id << 1, l, mid, u, v, val);
}

void solve() {
  int n;
  cin >> n;
  vector<i64> a(n + 1), p(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = p[i - 1] + a[i];
    upd(1, 0, n, i, 1e18);
  }
  vector<int> d(n + 1);
  for (int i = 1; i <= n; i++) {
    int pv = get(1, 0, n, 0, i, p[i]);
    d[i] = d[pv] + 1;
    upd(1, 0, n, i, p[i] * 2 - p[pv]);
  }
  cout << d[n];
  //[l, r] [r + 1, v]
  //p[r] - p[l - 1] <= p[v] - p[r]
  //2p[r] - p[l - 1] <= p[v]
}

int main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  int TC = 1;
  //cin >> TC;
  while (TC--) {
    solve();
  }
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27