Submission #524243

#	Time	Username	Problem	Language	Result	Execution time	Memory
524243		inluminas	Bigger segments (IZhO19_segments)	C++17	100 / 100	244 ms	25200 KiB

segments

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=5e5+5;
ll tree[4*lmt];

void update(int at,int L,int R,int pos,ll val){
  if(L==R){
    tree[at]=val;
    return;
  }
  int mid=(L+R)>>1;
  if(pos<=mid) update(at*2,L,mid,pos,val);
  else update(at*2+1,mid+1,R,pos,val);
  tree[at]=max(tree[at*2],tree[at*2+1]);
}

int find(int at,int L,int R,int l,int r,ll u){
  if(r<L || R<l || r<l) return 0;
  int mid=(L+R)>>1;
  if(l<=L && R<=r){
    if(L==R){
      if(tree[at]<u) return 0;
      return L;
    }

    if(tree[at*2+1]>=u) return find(at*2+1,mid+1,R,l,r,u);
    else if(tree[at*2]>=u) return find(at*2,L,mid,l,r,u);
    else return 0;
  }
  int y=find(at*2+1,mid+1,R,l,r,u);
  if(y) return y;
  return find(at*2,L,mid,l,r,u);
}

int main(){
  fastio;

  int n;
  cin>>n;

  ll pre[n+1],dp[n+1],ans[n+1];
  pre[0]=0;

  for(int i=1;i<=n;i++){
    ll x;
    cin>>x;
    pre[i]=pre[i-1]+x;
    update(1,1,n,i,-1e14);
  } 

  ans[0]=0;

  for(int i=1;i<=n;i++){
    int idx=find(1,1,n,1,i,pre[n]-pre[i]);

    dp[i]=pre[i]-pre[idx],ans[i]=ans[idx]+1;

    update(1,1,n,i,pre[n]-pre[i]-dp[i]);
  }

  cout<<ans[n]<<endl;
  return 0;
}

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