Submission #524234

#	Time	Username	Problem	Language	Result	Execution time	Memory
524234		inluminas	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	204 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;
array<ll,3>t[lmt];

int main(){
  fastio;

  int n;
  cin>>n;

  for(int i=0;i<=n;i++){
    t[i][0]=-inf;
  }

  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;
  }
  set<array<ll,3>>s;
  for(int i=1;i<=n;i++){

    auto it=s.lower_bound({pre[n]-pre[i],-inf,-inf});
    if(it==s.end()){
      dp[i]=pre[i],ans[i]=1;
      
      //t.insert({dp[i],-i,pre[n]-pre[i]-dp[i]});

      int ii=(int)ans[i];

      if(pre[n]-pre[i]-dp[i]>t[ii][0]){
        s.erase({t[ii][0],t[ii][1],t[ii][2]});
        t[ii][0]=pre[n]-pre[i]-dp[i],t[ii][1]=-i,t[ii][2]=dp[i];
        s.insert({pre[n]-pre[i]-dp[i],-i,dp[i]});
      }

    }else{
      int idx=-(*it)[1];
      dp[i]=pre[i]-pre[idx],ans[i]=ans[idx]+1;

      /*while(!t.empty()){
        it=t.end();
        it--;
        if(dp[i]<(*it)[0]){
          s.erase({ (*it)[2], (*it)[1], (*it)[0] });
          t.erase(it); 
        }else break;
      }*/

      int ii=(int)ans[i];


      if(pre[n]-pre[i]-dp[i]>t[ii][0]){
        s.erase({t[ii][0],t[ii][1],t[ii][2]});
        t[ii][0]=pre[n]-pre[i]-dp[i],t[ii][1]=-i,t[ii][2]=dp[i];
        s.insert({pre[n]-pre[i]-dp[i],-i,dp[i]});
      }

      
      //t.insert({dp[i],-i,pre[n]-pre[i]-dp[i]});     
    }
    //cout<<pre[n]-pre[i]-dp[i]<<" "<<ans[i]<<" "<<dp[i]<<endl;
  }

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

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