Submission #1228836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228836		rxlfd314	Distributing Candies (IOI21_candies)	C++17	38 / 100	220 ms	39496 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)

ll CAP;

struct Node {
  ll min_val, max_val, pre_min, pre_max, sum;
  Node operator+(const Node &other) {
    const auto apply = [&](const ll v) {
      if (v + other.pre_min < 0)
        return other.min_val;
      if (v + other.pre_max > CAP)
        return other.max_val;
      return v + other.sum;
    };
    return {apply(min_val), apply(max_val), min(pre_min, sum + other.pre_min), max(pre_max, sum + other.pre_max), sum + other.sum};
  }
};

struct ST {
  const int N;
  vt<Node> st;
  ST(const int n) : N(n), st(n << 1, {0, CAP, 0, 0, 0}) {}
  void update(int i, const ll v) {
    st[i += N] = {min(CAP, max(v, 0ll)), max(0ll, CAP + min(v, 0ll)), min(v, 0ll), max(v, 0ll), v};
    while (i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  };
  Node query(int l, int r) {
    Node lft = {0, CAP, 0, 0, 0};
    Node rht = {0, CAP, 0, 0, 0};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        lft = lft + st[l++];
      if (r & 1)
        rht = st[--r] + rht;
    }
    return lft + rht;
  }
};

vt<int> distribute_candies(vt<int> C, vt<int> L, vt<int> R, vt<int> V) {
  const int N = size(C), Q = size(L);
  if (*max_element(all(L)) == 0 && *min_element(all(R)) == N-1) {
    vt<ll> psum(Q), pmax(Q);
    psum[0] = V[0];
    pmax[0] = max(V[0], 0);
    FOR(i, 1, Q-1) {
      psum[i] = psum[i-1] + V[i];
      pmax[i] = max(pmax[i-1], psum[i]);
    }
    vt<ll> smin(Q), smax(Q);
    ll cur = LLONG_MIN;
    CAP = 1e18;
    ST st(Q);
    ROF(i, Q-1, 0) {
      st.update(i, V[i]);
      cur = max(cur, psum[i]);
      smin[i] = psum[i] - pmax[i];
      smax[i] = cur - psum[i];
      if (i + 1 < Q) {
        smin[i] = min(smin[i], smin[i+1]);
        smax[i] = max(smax[i], smax[i+1]);
      }
    }
    vt<int> next_zero(Q);
    ROF(i, Q-1, 0) {
      int lo = i + 1, hi = Q;
      while (lo < hi) {
        const int mid = lo + hi >> 1;
        if (st.query(i+1, mid).pre_min < 0)
          hi = mid;
        else
          lo = mid + 1;
      }
      next_zero[i] = lo < Q ? next_zero[lo] : i;
    }
    #ifdef DEBUG
    cout << "Bruh:\n";
    FOR(i, 0, Q-1)
      cout << psum[i] << "\n "[i+1<Q];
    FOR(i, 0, Q-1)
      cout << smin[i] << "\n "[i+1<Q];
    FOR(i, 0, Q-1)
      cout << smax[i] << "\n "[i+1<Q];
    FOR(i, 0, Q-1)
      cout << pmax[i] << "\n "[i+1<Q];
    FOR(i, 0, Q-1)
      cout << next_zero[i] << "\n "[i+1<Q];
    #endif
    vt<int> ret(N);
    FOR(i, 0, N-1) {
      int j = upper_bound(all(smin), -C[i]) - smin.begin() - 1;
      if (j >= 0)
        j = next_zero[j];
      else {
        int lo = 0, hi = Q;
        while (lo < hi) {
          const int mid = lo + hi >> 1;
          if (st.query(0, mid).pre_min < 0)
            hi = mid;
          else
            lo = mid + 1;
        }
        j = lo < Q ? next_zero[lo] : -1;
      }
      const ll v = st.query(j+1, Q-1).min_val - max(0ll, (j >= 0 ? smax[j] : cur) - C[i]);
      assert((j >= 0 ? smax[j] : cur) == st.query(j+1, Q-1).pre_max);
      assert(0 <= v && v <= C[i]);
      ret[i] = v;
    }
    return ret;
  }
  if (*min_element(all(C)) == *max_element(all(C))) {
    CAP = C[0];
    vt<vt<int>> ins(N), rem(N);
    FOR(i, 0, Q-1) {
      ins[L[i]].push_back(i);
      rem[R[i]].push_back(i);
    }
    ST st(Q);
    vt<int> ret(N);
    FOR(i, 0, N-1) {
      for (const auto &j : ins[i])
        st.update(j, V[j]);
      ret[i] = st.query(0, Q-1).min_val;
      for (const auto &j : rem[i])
        st.update(j, 0);
    }
    return ret;
  }
  if (max(N, Q) <= 2000) {
    vt<int> ans(N);
    FOR(i, 0, N-1)
      FOR(j, 0, Q-1)
        if (L[j] <= i && i <= R[j]) {
          ans[i] += V[j];
          ans[i] = min(ans[i], C[i]);
          ans[i] = max(ans[i], 0);
        }
    return ans;
  }
  if (*min_element(all(V)) > 0) {
    vt<ll> psum(N);
    FOR(i, 0, Q-1) {
      psum[L[i]] += V[i];
      if (R[i] + 1 < N)
        psum[R[i] + 1] -= V[i];
    }
    FOR(i, 0, N-1) {
      if (i)
        psum[i] += psum[i-1];
      C[i] = min((ll)C[i], psum[i]);
    }
    return C;
  }
}

Compilation message (stderr)

candies.cpp: In function 'vt<int> distribute_candies(vt<int>, vt<int>, vt<int>, vt<int>)':
candies.cpp:169:1: warning: control reaches end of non-void function [-Wreturn-type]
  169 | }
      | ^

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