Submission #522780

#	Time	Username	Problem	Language	Result	Execution time	Memory
522780		inluminas	Divide and conquer (IZhO14_divide)	C++17	100 / 100	69 ms	9556 KiB

divide

#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=1e5+10;
int mn[lmt*3];

struct id{
  ll val=0,p=0,d=0,g=0;
};

void build(int at,int L,int R){
  if(L==R){
    mn[at]=INT_MAX;
    return;
  }
  int mid=(L+R)>>1;
  build(at*2,L,mid);
  build(at*2+1,mid+1,R);
  mn[at]=INT_MAX;
}

void update(int at,int L,int R,int pos,int val){
  if(L==R){
    mn[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);
  mn[at]=min(mn[at*2],mn[at*2+1]);
}

int query(int at,int L,int R,int l,int r){
  if(r<L || R<l || r<l) return INT_MAX;
  if(l<=L && R<=r) return mn[at];
  int mid=(L+R)>>1;
  int x=query(at*2,L,mid,l,r),y=query(at*2+1,mid+1,R,l,r);
  return min(x,y);
}

int main(){
  fastio;

  ll n,ans=0;
  cin>>n;
  build(1,1,n);
  id a[n+1];
  for(int i=1;i<=n;i++){
    cin>>a[i].p>>a[i].g>>a[i].d;
    ans=max(ans,a[i].g);
  }
  if(n==1){
    cout<<ans<<endl;
    return 0;
  }
  for(int i=n-1;i>0;i--){
    a[i].val=a[i+1].p-a[i].p;
  }
  a[n].val=0;
  vector<array<ll,2>>c;
  for(int i=1;i<=n;i++){
    a[i].val=a[i].d-a[i].val;
    a[i].val+=a[i-1].val;
    a[i].g+=a[i-1].g;
    c.push_back({a[i].val,i});
  }


  int poi[n+1];
  memset(poi,0,sizeof poi);
  sort(c.begin(),c.end());
  int idx=0;
  for(auto [u,v]:c){
    poi[v]=++idx;
  }

  update(1,1,n,poi[1],1);
  for(int i=2;i<=n;i++){
    if(a[i-1].val+a[i].d>=0) ans=max(ans,a[i].g);
    int lo=0,hi=n-1;
    while(hi-lo>1){
      int mid=(lo+hi)>>1;
      if(c[mid][0]<=a[i-1].val+a[i].d) lo=mid;
      else hi=mid;
    }
    int idx=-1;
    if(c[hi][0]<=a[i-1].val+a[i].d) idx=hi+1;
    else if(c[lo][0]<=a[i-1].val+a[i].d) idx=lo+1;

    if(idx==-1){
      update(1,1,n,poi[i],i);
      continue;
    }

    idx=query(1,1,n,1,idx);
    
    if(idx==INT_MAX){
      update(1,1,n,poi[i],i);
      continue;
    }
    if(a[i].d+a[i-1].val-a[idx].val<0){
      update(1,1,n,poi[i],i);
      continue;
    }
    ans=max(ans,a[i].g-a[idx].g);
    update(1,1,n,poi[i],i);
  }
  cout<<ans<<endl;
  return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52