Submission #1229940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229940		rxlfd314	Distributing Candies (IOI21_candies)	C++17	100 / 100	297 ms	42808 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct Node {
  ll pre_max, pre_min, sum;
  Node operator+(const Node &other) const {
    return {max(pre_max, sum + other.pre_max), min(pre_min, sum + other.pre_min), sum + other.sum};
  }
};

constexpr Node ID = {(ll)-1e18, (ll)1e18, 0};

struct ST {
  vt<Node> st;
  ST(const int n) : st(n << 2, ID) {}
  #define lc i << 1
  #define rc lc | 1
  void update(const int p, const ll v, const int i, const int tl, const int tr) {
    if (tl == tr)
      st[i] = v < LLONG_MAX ? Node{v, v, v} : ID;
    else {
      const int tm = tl + tr >> 1;
      if (p <= tm)
        update(p, v, lc, tl, tm);
      else
        update(p, v, rc, tm+1, tr);
      st[i] = st[lc] + st[rc];
    }
  }
  void update(const int p, const ll v) {
    update(p, v, 1, 0, (size(st) >> 2) - 1);
  }
  int walk(const int v, const int i, const int tl, const int tr, const ll sum, const ll smax, const ll smin) {
    if (tl == tr)
      return tl;
    const int tm = tl + tr >> 1;
    const ll mx = max(smax, sum + st[lc].sum + st[rc].pre_max);
    const ll mn = min(smin, sum + st[lc].sum + st[rc].pre_min);
    if (mx - mn > v)
      return walk(v, rc, tm+1, tr, sum + st[lc].sum, smax, smin);
    return walk(v, lc, tl, tm, sum, mx, mn);
  }
  int walk(const int v) {
    return walk(v, 1, 0, (size(st) >> 2) - 1, 0, LLONG_MIN, LLONG_MAX);
  }
  Node query(const int ql, const int qr, const int i, const int tl, const int tr) {
    if (tl > qr || tr < ql)
      return ID;
    if (ql <= tl && tr <= qr)
      return st[i];
    const int tm = tl + tr >> 1;
    return query(ql, qr, lc, tl, tm) + query(ql, qr, rc, tm+1, tr);
  }
  Node query(const int ql, const int qr) {
    return query(ql, qr, 1, 0, (size(st) >> 2) - 1);
  }
  #undef lc
  #undef rc
};

vt<int> distribute_candies(vt<int> C, vt<int> L, vt<int> R, vt<int> V) {
  const int N = size(C), Q = size(L);
  V.insert(V.begin(), 0);
  vt<vt<int>> ins(N), rem(N);
  FOR(i, 0, Q-1) {
    ins[L[i]].push_back(i+1);
    rem[R[i]].push_back(i+1);
  }
  ST st(Q+1);
  st.update(0, 0);
  vt<int> ret(N);
  FOR(i, 0, N-1) {
    for (const auto &j : ins[i])
      st.update(j, V[j]);
    if (st.st[1].pre_max - st.st[1].pre_min <= C[i]) {
      ret[i] = st.st[1].sum - st.st[1].pre_min;
    } else {
      const Node v = st.query(st.walk(C[i])+1, Q);
      ret[i] = (v.sum > 0 ? C[i] - (v.pre_max - v.sum) : v.sum - v.pre_min);
    }
    for (const auto &j : rem[i])
      st.update(j, LLONG_MAX);
  }
  return ret;
}

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