Submission #1229883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229883		rxlfd314	사탕 분배 (IOI21_candies)	C++17	67 / 100	295 ms	39612 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+1);
    FOR(i, 0, Q-1)
      psum[i+1] = psum[i] + V[i];
    vt<ll> smax = psum, smin = psum;
    ROF(i, Q-1, 0) {
      smax[i] = max(smax[i+1], smax[i]);
      smin[i] = min(smin[i+1], smin[i]);
    }
    vt<int> ret(N);
    FOR(i, 0, N-1) {
      if (smax[0] - smin[0] <= C[i]) {
        ret[i] = psum[Q] - smin[0];
      } else {
        int lo = 0, hi = Q;
        while (lo < hi) {
          const int mid = lo + hi + 1 >> 1;
          if (smax[mid] - smin[mid] > C[i])
            lo = mid;
          else
            hi = mid - 1;
        }
        ret[i] = (psum[lo] < psum[Q] ? C[i] - (smax[lo] - psum[Q]) : psum[Q] - smin[lo]);
      }
    }
    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:126:1: warning: control reaches end of non-void function [-Wreturn-type]
  126 | }
      | ^

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