Submission #336071

#	Time	Username	Problem	Language	Result	Execution time	Memory
336071		Pety	Bigger segments (IZhO19_segments)	C++14	100 / 100	192 ms	23956 KiB

segments

#include <bits/stdc++.h>

using namespace std;

const int N = 500002;
int n, x, a[N];
int dp[N];
long long sum[N], aint[4*N];

void update (int nod, int st, int dr, int pozhatz, long long val) {
  if (st == dr) {
    aint[nod] = val;
    return;
  }
  int mid = (st + dr) / 2;
  if (pozhatz <= mid)
    update(2 * nod, st, mid, pozhatz, val);
  else
    update(2 * nod + 1, mid + 1, dr, pozhatz, val);
  aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}

int query (int nod, int st, int dr, long long lvl) {
  if (st == dr)
    return st;
  int mid = (st + dr) / 2;
  if (aint[2 * nod + 1] <= lvl)
    return query(2* nod + 1, mid + 1, dr,  lvl);
  else
    return query(2 * nod, st, mid,  lvl);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
  }
  for (int i = 1; i <= 4*n; i++)
    aint[i] = 1e18;
  int val;
  for (int i = 1; i <= n; i++) {
    if (aint[1] > sum[i])
      val = 0;
    else
      val = query(1, 1, n, sum[i]);
    dp[i] = dp[val] + 1;
    update(1, 1, n, i, 2 * sum[i] - sum[val]);
  }
  cout << dp[n];
  return 0;
}

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