#369214 (C++17) No.865 24時間降水量

• 問題: No.865 24時間降水量
• ユーザー: ngtkana
• 提出日時: 2019-08-16 21:39:25
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,585 bytes
• コンパイル時間: 2,856 ms
• コンパイル使用メモリ: 204,168 KB
• 最終ジャッジ日時: 2025-01-07 12:13:06
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 15 TLE * 3

ソースコード

#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_geneous = 0; ngtkana_is_geneous < n; ngtkana_is_geneous++)
#define rep(i, begin, end) for(int i = begin; i < end; i++)

#define LOCAL
using std::to_string;
auto to_string(std::string s) -> std::string {
  return '"' + s + '"';
}
auto to_string(char c) -> std::string {
  return "'" + std::string{c} + "'";
}
auto to_string(const char* s) -> std::string {
  return to_string((std::string) s);
}
auto to_string(bool b) -> std::string {
  return (b ? "true" : "false");
}
template <typename T, typename U>
auto to_string(std::pair<T, U> p) -> std::string {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <size_t N>
auto to_string(std::bitset<N> bs) -> std::string {
  std::string res{};
  for (size_t i = 0; i < N; i++)
    res.insert(res.begin(), bs.test(i) ? '1' : '0');
  return res;
}
template <typename T>
auto to_string(T v) -> std::string {
  bool flg = false;
  std::string res = "{";
  for (auto const&x : v) {
    if (flg) res += ", ";
    else flg = true;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<typename Value, typename BinaryOp>
class segment_tree
{
  public:
    using size_type      = int;
    using value_type     = Value;
    using function_type  = BinaryOp;
    using container_type = std::vector<value_type>;

  private:
    size_type       n, N;
    function_type   op;
    value_type      id;
    container_type  table;

    void cal (size_type u)
    {
      table.at(u) = op(table.at(2 * u), table.at(2 * u + 1));
    }

  public:
    segment_tree(int size, BinaryOp op, Value id, const std::vector<Value>& v):
      n     (std::pow(2, int(std::log2(size)) + 1)),
      N     (n * 2),
      op    (op),
      id    (id),
      table (N, id)
    {
      assert(n > 0);
      std::move(v.begin(), v.end(), table.begin() + n);
      for (size_type i = n - 1; i != 0; i--) cal(i);
    }

    segment_tree(int size, BinaryOp op, Value id):
      segment_tree(size, std::move(op), id, std::vector<Value>(size, id))
      {}

    auto at (size_type i) const -> value_type
    {
      return table.at(n + i);
    }

    auto query (size_type l, size_type r) const -> value_type
    {
      struct state {size_type top, left, right;};

      auto ret = id;
      std::stack<state> stk; stk.push({1, 0, n});
      while (!stk.empty())
      {
        auto now = stk.top(); stk.pop();
        if (l <= now.left && now.right <= r)
        {
          ret = op(ret, table.at(now.top));
          continue;
        }
        size_type mid = (now.left + now.right) / 2;
        if (l < mid) stk.push({2 * now.top,     now.left,  mid});
        if (mid < r) stk.push({2 * now.top + 1, mid, now.right});
      }
      return ret;
    }

    void update (size_type u, value_type val)
    {
      table.at(u += n) = val;
      for (u /= 2; u != 0; u /= 2) cal(u);
    }

    void add (size_type u, value_type val)
    {
      update(u, at(u) + val);
    }
};

template<typename Value, typename BinaryOp>
auto make_segment_tree(int size, BinaryOp op, Value vid)
{
  return segment_tree<Value, BinaryOp>(size, std::move(op), vid);
}

template<typename Value, typename BinaryOp>
auto make_segment_tree(int size, BinaryOp op, Value vid, std::vector<int> v)
{
  return segment_tree<Value, BinaryOp>(size, std::move(op), vid, std::move(v));
}

template<typename T, typename U>
inline auto cmn (T& a, U b) {if (a > b) {a = b; return true;} return false;}
template<typename T, typename U>
inline auto cmx (T& a, U b) {if (a < b) {a = b; return true;} return false;}

int main()
{
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<int> a(n);
  for (auto & x : a) std::cin >> x;
  auto sum_tree = make_segment_tree
  (
    n,
    [](auto x, auto y){return x + y;},
    0,
    a
  );
  int k = 24;
  int max = 0;
  for (int i = 0; i < n - k + 1; i++)
  {
    cmx(max, sum_tree.query(i, i + k));
  }
  int q; std::cin >> q;
  while (q--)
  {
    int t, v; std::cin >> t >> v;
    t--;
    sum_tree.update(t, v);
    for (int i = -k + 1; i < k; i++)
    {
      int l = t + i, r = l + k;
      if (l < 0 || n < r) continue;
      cmx(max, sum_tree.query(l, r));
    }
    std::cout << max << std::endl;
  }
  return 0;
}