제출 #1319387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319387		Johan	Bigger segments (IZhO19_segments)	C++20	73 / 100	34 ms	13320 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], n, best = 0;
array < int , 2 > st[N * 4];
array < int , 2 > merge(array < int , 2 > l, array < int , 2 > r){
  if(l[0] < r[0])return l;
  if(l[0] > r[0])return r;
  array < int , 2 > rs = l;
  if(l[1] < r[1])rs[1] = r[1];
  return rs; 
}
void upd(int v, int l, int r, int pos, int val){
  if(l == r){
    st[v] = {val, pos};
    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] = merge(st[v * 2], st[v * 2 + 1]);
}
void ask(int v, int l, int r, int cur){
  if(st[v][0] <= cur)
    best = max(best, st[v][1]);
  if(l == r)return;
  int mid = (l + r) >> 1;
  if(st[v * 2 + 1][0] <= cur)ask(v * 2 + 1, mid + 1, r, cur);
  else ask(v * 2, l, mid, cur);
}
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++){
    best = 0;
    ask(1, 0, n, pr[i]);
    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: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 0 / 27