#787542 (C++17) No.925 紲星 Extra

提出ソース

結果

問題	No.925 紲星 Extra
ユーザー	hashiryo
提出日時	2022-08-12 20:21:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5,555 ms / 10,000 ms
コード長	11,544 bytes
コンパイル時間	4,047 ms
コンパイル使用メモリ	248,692 KB
実行使用メモリ	13,596 KB
最終ジャッジ日時	2023-10-24 06:04:20
合計ジャッジ時間	53,759 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	19 ms 4,348 KB
testcase_04	AC	28 ms 4,348 KB
testcase_05	AC	2,698 ms 11,580 KB
testcase_06	AC	2,723 ms 11,484 KB
testcase_07	AC	2,717 ms 11,484 KB
testcase_08	AC	1,801 ms 5,352 KB
testcase_09	AC	1,270 ms 5,352 KB
testcase_10	AC	2,956 ms 10,164 KB
testcase_11	AC	2,592 ms 12,808 KB
testcase_12	AC	2,126 ms 10,692 KB
testcase_13	AC	2,188 ms 11,484 KB
testcase_14	AC	1,791 ms 5,352 KB
testcase_15	AC	2,011 ms 11,484 KB
testcase_16	AC	4,264 ms 9,848 KB
testcase_17	AC	5,555 ms 7,620 KB
testcase_18	AC	3,183 ms 11,484 KB
testcase_19	AC	3,867 ms 9,644 KB
testcase_20	AC	2,351 ms 13,332 KB
testcase_21	AC	1,744 ms 13,596 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#ifndef TEMP
#define TEMP
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &x) {
  return os << "(" << x.first << ", " << x.second << ")";
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
  os << '[';
  for (int _ = 0, __ = vec.size(); _ < __; _++) os << (_ ? ", " : "") << vec[_];
  return os << ']';
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &s) {
  os << '{';
  int _ = 0;
  for (const auto &x : s) os << (_++ ? ", " : "") << x;
  return os << '}';
}
template <typename T, std::size_t _Nm>
std::ostream &operator<<(std::ostream &os, const std::array<T, _Nm> &arr) {
  os << '[' << arr[0];
  for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_];
  return os << ']';
}
template <class Tup, std::size_t... I>
void print(std::ostream &os, const Tup &x, std::index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{(os << std::get<I>(x) << ", ", 0)...};
}
template <class... Args>
std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &x) {
  static constexpr std::size_t N = sizeof...(Args);
  os << "(";
  if constexpr (N >= 2) print(os, x, std::make_index_sequence<N - 1>());
  return os << std::get<N - 1>(x) << ")";
}
std::ostream &operator<<(std::ostream &os, std::int8_t x) {
  return os << (int)x;
}
std::ostream &operator<<(std::ostream &os, std::uint8_t x) {
  return os << (int)x;
}
std::ostream &operator<<(std::ostream &os, const __int128_t &v) {
  if (v == 0) os << "0";
  __int128_t tmp = v < 0 ? (os << "-", -v) : v;
  std::string s;
  while (tmp) s += '0' + (tmp % 10), tmp /= 10;
  return std::reverse(s.begin(), s.end()), os << s;
}
std::ostream &operator<<(std::ostream &os, const __uint128_t &v) {
  if (v == 0) os << "0";
  __uint128_t tmp = v;
  std::string s;
  while (tmp) s += '0' + (tmp % 10), tmp /= 10;
  return std::reverse(s.begin(), s.end()), os << s;
}
#ifdef __LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m",
                  BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m",
                  NORMAL_CROSSED = "\033[0;9;37m", ITALIC = "\033[3m",
                  BOLD = "\033[1m", RED_BACKGROUND = "\033[1;41m",
                  NORMAL_FAINT = "\033[0;2m";
#define func_LINE_FILE                                                 \
  NORMAL_FAINT << " in " << BOLD << __func__ << NORMAL_FAINT << ITALIC \
               << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET
#define checkpoint() \
  std::cerr << BRIGHT_RED << "< check point! >" << func_LINE_FILE << '\n'
#define debug(x)                                                \
  std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
            << func_LINE_FILE << '\n'
#define debugArray(x, n)                                             \
  do {                                                               \
    std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = [" << x[0]; \
    for (int _ = 1; _ < (int)(n); ++_) std::cerr << ", " << x[_];    \
    std::cerr << "]" << func_LINE_FILE << '\n';                      \
  } while (0)
#define debugMatrix(x, h, w)                                       \
  do {                                                             \
    std::cerr << BRIGHT_CYAN << #x << "\n" << COLOR_RESET << "= "; \
    for (int _ = 0; (_) < (int)(h); ++_) {                         \
      std::cerr << ((_ ? "   [" : "[["));                          \
      for (int __ = 0; __ < (int)(w); ++__)                        \
        std::cerr << ((__ ? ", " : "")) << x[_][__];               \
      std::cerr << "]" << (_ + 1 == (int)(h) ? "]" : ",\n");       \
    }                                                              \
    std::cerr << func_LINE_FILE << '\n';                           \
  } while (0)
#else
#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

template <class T>
auto compress(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  return
      [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}

struct ClosedSection {
  long long l, r;
  ClosedSection() : l(1), r(0) {}
  ClosedSection(long long l_, long long r_) : l(l_), r(r_) {}
  bool valid() { return l <= r; }
};
template <class Check>  // closed [l,r]
ClosedSection bin_search(const Check &isok, long long l, long long r) {
  bool res_l = isok(l), res_r = isok(r);
  if (res_l && res_r) return ClosedSection(l, r);
  if (!res_l && !res_r) return ClosedSection();
  long long lb = l, ub = r;
  for (long long x; ub - lb > 1;)
    (isok(x = (lb + ub) / 2) == res_l ? lb : ub) = x;
  return res_l ? ClosedSection(l, lb) : ClosedSection(ub, r);
}
template <class Check>
ClosedSection bin_search(const Check &isok, ClosedSection cs) {
  return cs.valid() ? bin_search(isok, cs.l, cs.r) : cs;
}
#endif

template <class T>
class RangeChminChmaxAddSumQuery {
  static constexpr std::size_t INF = std::numeric_limits<T>::max() / 2;
  struct Dat {
    const std::size_t n;
    std::vector<T> a, sorted, acc;
    T add, lb, ub;
    Dat(std::size_t b)
        : n(b), a(n, 0), sorted(a), acc(n + 1, 0), add(0), lb(-INF), ub(INF) {}
    Dat(const T *bg, std::size_t b)
        : n(b), a(bg, bg + n), acc(n + 1, 0), add(0), lb(-INF), ub(INF) {
      build();
    }
    inline bool eval() {
      if (add == 0 && lb == -INF && ub == INF) return false;
      for (auto &x : a) x = std::clamp(x, lb, ub) + add;
      return add = 0, lb = -INF, ub = INF, true;
    }
    inline void build() {
      sorted = a, std::sort(sorted.begin(), sorted.end());
      for (int i = 0; i < n; i++) acc[i + 1] = acc[i] + sorted[i];
    }
    inline std::size_t count(T x) const {
      if (x -= add; x <= lb) return 0;
      if (ub < x) return n;
      return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }
    inline T sum() const {
      std::size_t l = std::lower_bound(sorted.begin(), sorted.end(), lb) -
                      sorted.begin(),
                  u = std::lower_bound(sorted.begin(), sorted.end(), ub) -
                      sorted.begin();
      return acc[u] - acc[l] + lb * l + ub * (n - u) + add * n;
    }
    inline T sum(T x) const {
      if (x -= add; x <= lb) return 0;
      if (ub < x) return sum();
      std::size_t l = std::lower_bound(sorted.begin(), sorted.end(), lb) -
                      sorted.begin(),
                  u = std::lower_bound(sorted.begin(), sorted.end(), x) -
                      sorted.begin();
      return acc[u] - acc[l] + lb * l + add * u;
    }
    inline T get(std::size_t k) const { return std::clamp(a[k], lb, ub) + add; }
  };
  const std::size_t n, bsz;
  std::vector<Dat> dat;
  template <class U, class All, class One>
  inline U fold(std::size_t l, std::size_t r, const All &all,
                const One &one) const {
    U ret = 0;
    if (std::size_t i = l / bsz, j = r / bsz, k = l % bsz, m = r % bsz; i < j) {
      if (k) {
        for (; k < dat[i].n; k++) ret += one(dat[i].get(k));
        i++;
      }
      for (; i < j; i++) ret += all(dat[i]);
      if (m)
        for (; m--;) ret += one(dat[j].get(m));
    } else
      for (; k < m; k++) ret += one(dat[i].get(k));
    return ret;
  }
  template <class All, class One>
  inline void update(std::size_t l, std::size_t r, const All &all,
                     const One &one) {
    if (std::size_t i = l / bsz, j = r / bsz, k = l % bsz, m = r % bsz; i < j) {
      if (k) {
        for (dat[i].eval(); k < dat[i].n; k++) one(dat[i].a[k]);
        dat[i].build(), i++;
      }
      for (; i < j; i++) all(dat[i]);
      if (m) {
        for (dat[j].eval(); m--;) one(dat[j].a[m]);
        dat[j].build();
      }
    } else {
      for (dat[i].eval(); k < m; k++) one(dat[i].a[k]);
      dat[i].build();
    }
  }

 public:
  RangeChminChmaxAddSumQuery(std::size_t n_, std::size_t b = 100)
      : n(n_), bsz(b) {
    for (int l = 0, r; l < n; l = r)
      r = std::min(l + b, n), dat.emplace_back(r - l);
  }
  RangeChminChmaxAddSumQuery(const std::vector<T> &a, std::size_t b = 100)
      : n(a.size()), bsz(b) {
    for (int l = 0, r; l < n; l = r)
      r = std::min(l + b, n), dat.emplace_back(a.data() + l, r - l);
  }
  std::size_t count(std::size_t l, std::size_t r, T ub) const {
    return fold<std::size_t>(
        l, r, [&](const Dat &d) { return d.count(ub); },
        [&](T x) { return x < ub; });
  }
  std::size_t count(std::size_t l, std::size_t r, T lb, T ub) const {
    return count(l, r, ub) - count(l, r, lb);
  }
  T sum(std::size_t l, std::size_t r) const {
    return fold<T>(
        l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
  }
  T sum(std::size_t l, std::size_t r, T ub) const {
    return fold<T>(
        l, r, [&](const Dat &d) { return d.sum(ub); },
        [&](T x) { return x < ub ? x : 0; });
  }
  T sum(std::size_t l, std::size_t r, T lb, T ub) const {
    return sum(l, r, ub) - sum(l, r, lb);
  }
  void set(std::size_t k, T x) {
    std::size_t i = k / bsz, j = k % bsz;
    dat[i].eval(), dat[i].a[j] = x, dat[i].build();
  }
  T get(std::size_t k) const { return dat[k / bsz].get(k % bsz); }
  T operator[](std::size_t k) const { return get(k); }
  void add(std::size_t l, std::size_t r, T v) {
    update(
        l, r, [&](Dat &d) { d.add += v; }, [&](T &x) { x += v; });
  }
  void chmin(std::size_t l, std::size_t r, T ub) {
    update(
        l, r,
        [&](Dat &d) {
          T b = ub - d.add;
          d.ub = std::min(d.ub, b), d.lb = std::min(d.lb, b);
        },
        [&](T &x) { x = std::min(x, ub); });
  }
  void chmax(std::size_t l, std::size_t r, T lb) {
    update(
        l, r,
        [&](Dat &d) {
          T a = lb - d.add;
          d.lb = std::max(d.lb, a), d.ub = std::max(d.ub, a);
        },
        [&](T &x) { x = std::max(x, lb); });
  }
  void chclamp(std::size_t l, std::size_t r, T lb, T ub) {
    update(
        l, r,
        [&](Dat &d) {
          T a = lb - d.add, b = ub - d.add;
          d.ub = std::clamp(d.ub, a, b), d.lb = std::clamp(d.lb, a, b);
        },
        [&](T &x) { x = std::clamp(x, lb, ub); });
  }
};

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  RangeChminChmaxAddSumQuery<long long> sqrtdc(a, 710);
  long long s = 0;
  tree<long long, null_type, less<long long>, rb_tree_tag,
       tree_order_statistics_node_update>
      S(a.begin(), a.end());
  while (Q--) {
    int op;
    cin >> op;
    if (op == 1) {
      long long X, Y;
      cin >> X >> Y;
      (X ^= s) &= (1 << 16) - 1, (Y ^= s) &= (1ll << 40) - 1;
      X--;
      sqrtdc.set(X, Y);
      S.insert(Y);
    } else {
      int L, R;
      cin >> L >> R;
      (L ^= s) &= (1 << 16) - 1, (R ^= s) &= (1 << 16) - 1;
      if (L > R) swap(L, R);
      L--;
      int m = (R - L) / 2;
      auto cs = bin_search(
          [&](int i) { return sqrtdc.count(L, R, *S.find_by_order(i)) <= m; },
          0, S.size() - 1);
      long long x = *S.find_by_order(cs.r);
      long long ans = sqrtdc.sum(L, R) - sqrtdc.sum(L, R, x) * 2;
      ans -= x * (R - L - sqrtdc.count(L, R, x) * 2);
      cout << ans << '\n';
      s ^= ans;
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード