제출 #1228788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228788		rxlfd314	사탕 분배 (IOI21_candies)	C++17	11 / 100	157 ms	23624 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)

int 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, 0, 0}) {}
  void update(int i, const int v) {
    st[i += N] = {min(CAP, max(v, 0)), max(0, CAP + min(v, 0)), min(v, 0), max(v, 0), 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 (*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;
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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