Submission #851521

#	Time	Username	Problem	Language	Result	Execution time	Memory
851521		NeroZein	Bigger segments (IZhO19_segments)	C++17	100 / 100	153 ms	21180 KiB

segments

#include "bits/stdc++.h"
using namespace std;

const int N = 5e5 + 5;

int a[N];
int dp[N]; 
long long pref[N]; 

long long seg[N * 2];

void upd(int nd, int l, int r, int p, long long v) {
  if (l == r) {
    seg[nd] = v;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = min(seg[nd + 1], seg[rs]); 
}

int get(int nd, int l, int r, int s, int e, long long v) {
  if (l > e || r < s || seg[nd] > v) {
    return -1; 
  }
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  int ret = get(rs, mid + 1, r, s, e, v);
  if (ret == -1) {
    ret = get(nd + 1, l, mid, s, e, v);
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  fill(seg, seg + N * 2, 1e18);
  upd(0, 0, N, 0, 0); 
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pref[i] = pref[i - 1] + a[i]; 
  }
  dp[1] = 1;
  upd(0, 0, N, 1, a[1] * 2); 
  for (int i = 2; i <= n; ++i) {
    int j = get(0, 0, N, 0, i - 1, pref[i]); 
    dp[i] = dp[j] + 1;
    long long sum = pref[i] - pref[j];
    upd(0, 0, N, i, sum + pref[i]); 
  }
  cout << dp[n] << '\n';
  return 0;
}

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