結果

問題 No.2065 Sum of Min
ユーザー hashiryohashiryo
提出日時 2023-11-05 21:34:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,471 bytes
コンパイル時間 3,068 ms
コンパイル使用メモリ 213,320 KB
実行使用メモリ 9,796 KB
最終ジャッジ日時 2023-11-05 21:35:24
合計ジャッジ時間 24,956 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,372 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 2 ms
4,372 KB
testcase_04 AC 569 ms
9,796 KB
testcase_05 AC 1,131 ms
9,796 KB
testcase_06 AC 1,335 ms
9,796 KB
testcase_07 AC 804 ms
9,796 KB
testcase_08 AC 795 ms
9,796 KB
testcase_09 AC 61 ms
9,796 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 AC 1,038 ms
9,796 KB
testcase_13 AC 1,015 ms
9,796 KB
testcase_14 AC 1,035 ms
9,796 KB
testcase_15 AC 1,039 ms
9,796 KB
testcase_16 AC 1,053 ms
9,796 KB
testcase_17 AC 1,051 ms
9,796 KB
testcase_18 AC 1,024 ms
9,796 KB
testcase_19 AC 1,049 ms
9,796 KB
testcase_20 AC 1,042 ms
9,796 KB
testcase_21 AC 1,034 ms
9,796 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
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)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)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;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
template <class T, size_t B= 700> class SortedPerBucket {
 static constexpr T INF= std::numeric_limits<T>::max() / 2;
 struct Dat {
  const size_t n;
  T a[B], sorted[B], acc[B + 1];
  T add, lb, ub;
  Dat(size_t b): n(b), a{0}, sorted{0}, acc{0}, add(0), lb(-INF), ub(INF) {}
  Dat(const T *bg, size_t b): n(b), a{0}, acc{0}, add(0), lb(-INF), ub(INF) {
   for (int i= n; i--;) a[i]= *(bg + i);
   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() { std::copy_n(a, B, sorted), std::sort(sorted, sorted + n), std::partial_sum(sorted, sorted + n, acc + 1); }
  inline size_t idx(T x) const { return std::lower_bound(sorted, sorted + n, x) - sorted; }
  inline size_t count(T x) const { return x-= add, (x <= lb ? 0 : ub < x ? n : idx(x)); }
  inline T sum() const {
   size_t l= idx(lb), u= idx(ub);
   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();
   size_t l= idx(lb), u= idx(x);
   return acc[u] - acc[l] + lb * l + add * u;
  }
  inline T get(size_t k) const { return std::clamp(a[k], lb, ub) + add; }
 };
 const size_t n;
 std::vector<Dat> dat;
 template <class U, class All, class One> inline U fold(size_t l, size_t r, const All &all, const One &one) const {
  U ret= 0;
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; 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(size_t l, size_t r, const All &all, const One &one) {
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; 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:
 SortedPerBucket(size_t n): n(n) {
  for (int l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(r - l);
 }
 SortedPerBucket(const std::vector<T> &a): n(a.size()) {
  for (int l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(a.data() + l, r - l);
 }
 // count i s.t. (l <= i < r) && (a[i] < ub)
 size_t count(size_t l, size_t r, T ub) const {
  return fold<size_t>(
      l, r, [&](const Dat &d) { return d.count(ub); }, [&](T x) { return x < ub; });
 }
 // count i s.t. (l <= i < r) && (lb <= a[i] < ub)
 size_t count(size_t l, size_t r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
 // sum a[i] s.t. (l <= i < r)
 T sum(size_t l, size_t r) const {
  return fold<T>(
      l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
 }
 // sum a[i] s.t. (l <= i < r) && (a[i] < ub)
 T sum(size_t l, 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; });
 }
 // sum a[i] s.t. (l <= i < r)  && (lb <= a[i] < ub)
 T sum(size_t l, size_t r, T lb, T ub) const { return sum(l, r, ub) - sum(l, r, lb); }
 void set(size_t k, T x) {
  size_t i= k / B, j= k % B;
  dat[i].eval(), dat[i].a[j]= x, dat[i].build();
 }
 T get(size_t k) const { return dat[k / B].get(k % B); }
 T operator[](size_t k) const { return get(k); }
 void add(size_t l, size_t r, T v) {
  update(
      l, r, [&](Dat &d) { d.add+= v; }, [&](T &x) { x+= v; });
 }
 void chmin(size_t l, size_t r, T ub) {
  auto f= [&](Dat &d) {
   T b= ub - d.add;
   d.ub= std::min(d.ub, b), d.lb= std::min(d.lb, b);
  };
  update(l, r, f, [&](T &x) { x= std::min(x, ub); });
 }
 void chmax(size_t l, size_t r, T lb) {
  auto f= [&](Dat &d) {
   T a= lb - d.add;
   d.lb= std::max(d.lb, a), d.ub= std::max(d.ub, a);
  };
  update(l, r, f, [&](T &x) { x= std::max(x, lb); });
 }
 void chclamp(size_t l, size_t r, T lb, T ub) {
  auto f= [&](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);
  };
  update(l, r, f, [&](T &x) { x= std::clamp(x, lb, ub); });
 }
};
using namespace std;
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];
 SortedPerBucket<long long> spb(A);
 while (Q--) {
  int L, R, X;
  cin >> L >> R >> X, --L;
  cout << spb.sum(L, R, X) + (long long)(R - L - spb.count(L, R, X)) * X << '\n';
 }
 return 0;
}
0