Submission #1319152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319152		Johan	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	332 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int N = 2e5 + 5;
int a[N], pr[N], cur[N], dp[N][2], st[N * 4], n;
void upd(int v, int l, int r, int pos, int val){
  if(l == r){
    st[v] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if(mid >= pos)upd(v * 2, l, mid, pos, val);
  else upd(v * 2 + 1, mid + 1, r, pos, val);
  st[v] = min(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
  if(l > qr || r < ql)return INF;
  if(l >= ql && r <= qr)return st[v];
  int mid = (l + r) >> 1;
  return min(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
int get(int l, int r){
  return ask(1, 1, n, l, r);
}
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    pr[i] = pr[i - 1] + a[i];
    dp[i][0] = -1;
    dp[i][1] = INF;
    upd(1, 1, n, i, INF);
  }
  dp[1][0] = 1;
  dp[1][1] = a[1];
  upd(1, 1, n, 1, a[1] + pr[1]);
  for(int i = 2; i <= n; i++){
    int l = 0, r = i;
    int best = -1;
    while(r >= l){
      int mid = (l + r) >> 1;
      if(get(mid, i) <= pr[i]){
        best = mid;
        l = mid + 1;
      }
      else r = mid - 1;
      // cout << l << ' ' << r << '\n';
    }
    // for(int j = i; j >= 0; --j){
    //   if(get(j, j) <= pr[i]){
    //     best = j;
    //     break;
    //   }
    // }
    // cout << best << '\n';
    if(best == -1)continue;
    dp[i][1] = min(dp[i][1], pr[i] - pr[best]);
    upd(1, 1, n, i, dp[i][1] + pr[i]);
    dp[i][0] = dp[best][0] + 1;
  }
  cout << dp[n][0] << endl;
}   

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