Submission #760801

#	Time	Username	Problem	Language	Result	Execution time	Memory
760801		fuad27	Distributing Candies (IOI21_candies)	C++17	0 / 100	1205 ms	47680 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;
  int idn, idx;
  node(){}
  node(int at) {
    idn=idx=at;
  }
  node operator+(node B) {
   node res=(*this);
   if(res.mn>B.mn) {
    res.idn=B.idn;
   }
   if(res.mx<B.mx)res.idx=B.idx;
   res.mn=min(res.mn, B.mn);
   res.mx=max(res.mx, B.mx);
   return res;
  }
};
struct F1 {
  long long 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(int tl, int tr, int v) {
    lz[v]=F();
    if(tl==tr) {
      t[v]=node(tl);
      return;
    }
    int tm=(tl+tr)/2;
    build(tl,tm,2*v);
    build(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(){build(0,n-1,1);}
};
vector<int32_t> 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;
  st.build();
  vector<int32_t> 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, 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;
        lo=mid+1;
      }
      else {
        hi=mid-1;
      }
    }
    node rs=st.query(ress, q+1);
    if(rs.idn>rs.idx) {
      long long val=rs.mn;
      res[i]=st.query(q+1,q+1).mx-val;
    }
    else if(rs.idn<rs.idx){
      long long val=rs.mx;
      res[i]=st.query(q+1,q+1).mx-val+c[i];
    }
    else {
      res[i]=st.query(q+1,q+1).mx;
    }
  }
  return res;
}

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