Submission #760773

#	Time	Username	Problem	Language	Result	Execution time	Memory
760773		fuad27	Distributing Candies (IOI21_candies)	C++17	0 / 100	1796 ms	39956 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const int N_=200'010;
const long long INF=1e18;
struct node {
  long long mn=0, mx=0;
  node operator+(node B) {
   node res;
   res.mn=mn;
   res.mx=mx;
   res.mn=min(res.mn, B.mn);
   res.mx=max(res.mx, B.mx);
   return res;
  }
};
struct F1 {
  int add=0;
  F1(){}
  node applyAggregate(node res) {
    res.mn+=add;
    res.mx+=add;
    return res;
  }
  void compose(F1 par) {
    add+=par.add;
  }
};
template<typename T, typename F>
struct ST {
  vector<T> t;
  vector<F> lz;
  T def;
  int n;
  ST(){}
  ST(int N) {
    n=N;
    t=vector<T>(4*n);
    lz=vector<F>(4*n);
  }
  void build(T a[], int tl, int tr, int v) {
    lz[v]=F(tl,tr);
    if(tl==tr) {
      t[v]=a[tl];
      return;
    }
    int tm=(tl+tr)/2;
    build(a,tl,tm,2*v);
    build(a,tm+1,tr,2*v+1);
    t[v]=t[2*v]+t[2*v+1];
  }
  void push(int v) {
    lz[2*v].compose(lz[v]);
    lz[2*v+1].compose(lz[v]);
    t[v]=lz[v].applyAggregate(t[v]);
    lz[v]=F();
  }
  T query(int l, int r, int tl, int tr, int v) {
    if(l>tr or r<tl)return def;
    if(l<=tl and tr<=r)return lz[v].applyAggregate(t[v]);
    push(v);
    int tm=(tl+tr)/2;
    return query(l,r,tl,tm,2*v)+query(l,r,tm+1,tr,2*v+1);
  }
  void update(int l, int r, F upd, int tl, int tr, int v) {
    if(r<tl or tr<l)return;
    if(l<=tl and tr<=r) {
      lz[v].compose(upd);
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    update(l,r,upd,tl,tm,2*v);
    update(l,r,upd,tm+1,tr,2*v+1);
    t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
  }
  void update(int at, T val, int tl, int tr, int v) {
    if(tl==tr) {
      t[v]=val;
      lz[v]=F();
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    if(at<=tm)update(at,val,tl,tm,2*v);
    else update(at,val,tm+1,tr,2*v+1);
    t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
  }
  T query(int l, int r){return query(l,r,0,n-1,1);}
  void update(int l, int r, F upd){update(l,r,upd,0,n-1,1);}
  void update(int at, T val){update(at,val,0,n-1,1);}
  void build(T a[]){build(a,0,n-1,1);}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n=c.size(), q=l.size();
  ST<node, F1> st(q+2);
  st.def.mx=-INF;
  st.def.mn=INF;
  vector<int> res(n);
  vector<pair<int,long long>> ad[n+1];
  for(int i=0;i<q;i++) {
    ad[l[i]].push_back({i+1,v[i]});
    ad[r[i]+1].push_back({i+1,-v[i]});
  }
  for(int i = 0;i<n;i++) {
    for(auto to:ad[i]) {
      F1 lz;
      lz.add=to.second;
      st.update(to.first, q+1, lz);
    }
    int lo=0, hi=q+1;
    long long ress=0;
    while(lo<=hi) {
      int mid=(lo+hi)/2;
      node rs=st.query(mid, q+1);
      if(rs.mx-rs.mn<=c[i]) {
        ress=mid;
        hi=mid-1;
      }
      else {
        lo=mid+1;
      }
    }
    long long cur=st.query(ress,ress).mx;
    lo=0,hi=ress-1;
    long long resss=-1;
    while(lo<=hi) {
      int mid=(lo+hi)/2;
      node rs=st.query(mid,ress);
      if(rs.mx-rs.mn!=0) {
        resss=mid;
        lo=mid+1;
      }
      else {
        hi=mid-1;
      }
    }
//    cout << cur << " " << ress << endl;
    if(resss==-1) {
     resss=-1;
    }
    else {
      resss=st.query(resss,resss).mx;
    }
    if(resss>cur) {
      res[i]=st.query(q+1,q+1).mx-(cur);
    }
    else {
      res[i]=st.query(q+1,q+1).mx-(cur)+c[i];
    }
  }
  return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33