oj.uz

Submission #522766

# Submission time Handle Problem Language Result Execution time Memory
522766 2022-02-05T17:09:09 Z inluminas Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 204 KB 
#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 idx=query(1,1,n,1,poi[i]);
    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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -