#989412 (C++23) No.2758 RDQ

提出ソース

結果

問題	No.2758 RDQ
ユーザー	kusaf_
提出日時	2024-06-18 02:56:41
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,107 ms / 2,000 ms
コード長	5,570 bytes
コンパイル時間	4,362 ms
コンパイル使用メモリ	268,088 KB
実行使用メモリ	398,660 KB
最終ジャッジ日時	2024-06-18 02:57:08
合計ジャッジ時間	26,094 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,001 ms 398,536 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1,032 ms 398,532 KB
testcase_07	AC	972 ms 398,532 KB
testcase_08	AC	963 ms 398,660 KB
testcase_09	AC	983 ms 398,532 KB
testcase_10	AC	986 ms 398,532 KB
testcase_11	AC	1,073 ms 398,532 KB
testcase_12	AC	1,078 ms 398,532 KB
testcase_13	AC	1,095 ms 398,532 KB
testcase_14	AC	1,101 ms 398,536 KB
testcase_15	AC	1,101 ms 398,540 KB
testcase_16	AC	1,107 ms 398,536 KB
testcase_17	AC	1,072 ms 398,660 KB
testcase_18	AC	1,103 ms 398,572 KB
testcase_19	AC	1,099 ms 398,536 KB
testcase_20	AC	1,101 ms 398,412 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,940 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuccinctIndexableDictionary {
  ll len;
  ll blk;
  vector<ll> bit, sum;
  SuccinctIndexableDictionary() = default;
  SuccinctIndexableDictionary(ll len): len(len), blk((len + 31) >> 5) {
    bit.assign(blk, 0LL);
    sum.assign(blk, 0LL);
  }
  void set(ll k) { bit[k >> 5] |= 1LL << (k & 31); }
  void build() {
    sum[0] = 0LL;
    for(ll i = 1; i < blk; i++) { sum[i] = sum[i - 1] + __builtin_popcountll(bit[i - 1]); }
  }
  bool operator[](ll k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); }
  ll rank(ll k) { return (sum[k >> 5] + __builtin_popcountll(bit[k >> 5] & ((1LL << (k & 31)) - 1))); }
  ll rank(bool val, ll k) { return (val ? rank(k) : k - rank(k)); }
};

template<typename T, ll MAXLOG> struct WaveletMatrix {
  ll len;
  SuccinctIndexableDictionary mat[MAXLOG];
  ll mid[MAXLOG];
  WaveletMatrix() = default;
  WaveletMatrix(vector<T> v): len(v.size()) {
    vector<T> l(len), r(len);
    for(ll lev = MAXLOG - 1; lev >= 0; lev--) {
      mat[lev] = SuccinctIndexableDictionary(len + 1);
      ll left = 0, right = 0;
      for(ll i = 0; i < len; i++) {
        if(((v[i] >> lev) & 1)) {
          mat[lev].set(i);
          r[right++] = v[i];
        }
        else { l[left++] = v[i]; }
      }
      mid[lev] = left;
      mat[lev].build();
      v.swap(l);
      for(ll i = 0; i < right; i++) { v[left + i] = r[i]; }
    }
  }
  pair<ll, ll> succ(bool f, ll l, ll r, ll lev) { return {mat[lev].rank(f, l) + mid[lev] * f, mat[lev].rank(f, r) + mid[lev] * f}; }
  T access(ll k) {
    T ret = 0;
    for(ll lev = MAXLOG - 1; lev >= 0; lev--) {
      bool f = mat[lev][k];
      if(f) { ret |= T(1) << lev; }
      k = mat[lev].rank(f, k) + mid[lev] * f;
    }
    return ret;
  }
  T operator[](const ll &k) { return access(k); }
  ll rank(const T &x, ll r) {
    ll l = 0;
    for(ll lev = MAXLOG - 1; lev >= 0; lev--) { tie(l, r) = succ((x >> lev) & 1, l, r, lev); }
    return r - l;
  }
  T kth_smallest(ll l, ll r, ll k) {
    assert(0 <= k && k < r - l);
    T ret = 0;
    for(ll lev = MAXLOG - 1; lev >= 0; lev--) {
      ll cnt = mat[lev].rank(false, r) - mat[lev].rank(false, l);
      bool f = cnt <= k;
      if(f) {
        ret |= T(1) << lev;
        k -= cnt;
      }
      tie(l, r) = succ(f, l, r, lev);
    }
    return ret;
  }
  T kth_largest(ll l, ll r, ll k) { return kth_smallest(l, r, r - l - k - 1); }
  ll range_freq(ll l, ll r, T upper) {
    ll ret = 0;
    for(ll lev = MAXLOG - 1; lev >= 0; lev--) {
      bool f = ((upper >> lev) & 1);
      if(f) { ret += mat[lev].rank(false, r) - mat[lev].rank(false, l); }
      tie(l, r) = succ(f, l, r, lev);
    }
    return ret;
  }
  ll range_freq(ll l, ll r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); }
  T prev_value(ll l, ll r, T upper) {
    ll cnt = range_freq(l, r, upper);
    return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
  }
  T next_value(ll l, ll r, T lower) {
    ll cnt = range_freq(l, r, lower);
    return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
  }
};

template<typename T = ll, ll MAXLOG = 20> struct CompressedWaveletMatrix {
  WaveletMatrix<ll, MAXLOG> mat;
  vector<T> ys;
  CompressedWaveletMatrix() {}
  CompressedWaveletMatrix(const vector<T> &v): ys(v) {
    ranges::sort(ys);
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<ll> t(v.size());
    for(ll i = 0; i < (ll)v.size(); i++) { t[i] = get(v[i]); }
    mat = WaveletMatrix<ll, MAXLOG>(t);
  }
  inline ll get(const T &x) { return ranges::lower_bound(ys, x) - ys.begin(); }
  T access(ll k) { return ys[mat.access(k)]; }
  T operator[](const ll &k) { return access(k); }
  ll rank(const T &x, ll r) {  // count i s.t. (0<=i<r)&&v[i]==x
    auto pos = get(x);
    if(pos == (ll)ys.size() || ys[pos] != x) { return 0; }
    return mat.rank(pos, r);
  }
  ll count(ll l, ll r, T x) {  // count i s.t. (l<=i<r)&&v[i]==x
    if(l >= r) { return 0; }
    return rank(x, r) - rank(x, l);
  }
  T kth_smallest(ll l, ll r, ll k) { return ys[mat.kth_smallest(l, r, k)]; }  // k-th(0-indexed) smallest number in v[l,r)
  T kth_largest(ll l, ll r, ll k) { return ys[mat.kth_largest(l, r, k)]; }  // k-th(0-indexed) largest number in v[l,r)
  ll range_freq(ll l, ll r, T upper) {  // count i s.t. (l<=i<r)&&(v[i]<upper)
    if(l >= r) { return 0; }
    return mat.range_freq(l, r, get(upper));
  }
  ll range_freq(ll l, ll r, T lower, T upper) {  // count i s.t. (l<=i<r)&&(lower<=v[i]<upper)
    if(l >= r || lower >= upper) { return 0; }
    return mat.range_freq(l, r, get(lower), get(upper));
  }
  T prev_value(ll l, ll r, T upper) {  // max v[i] s.t. (l<=i<r)&&(v[i]<upper)
    auto ret = mat.prev_value(l, r, get(upper));
    return ret == -1 ? T(-1) : ys[ret];
  }
  T next_value(ll l, ll r, T lower) {  // min v[i] s.t. (l<=i<r)&&(lower<=v[i])
    auto ret = mat.next_value(l, r, get(lower));
    return ret == -1 ? T(-1) : ys[ret];
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N, Q;
  cin >> N >> Q;

  vector<ll> A(N);
  for(auto &i : A) { cin >> i; }

  vector<vector<ll>> v(1001, vector<ll>(N + 1, 0));
  for(ll i = 1; i <= 1000; i++) {
    for(ll j = 0; j < N; j++) {
      v[i][j + 1] = v[i][j] + !(A[j] % i);
    }
  }

  CompressedWaveletMatrix<> W(A);

  while(Q--) {
    ll l, r, k;
    cin >> l >> r >> k;
    l--;
    if(k <= 1000) { cout << v[k][r] - v[k][l] << "\n"; }
    else {
      ll ans = 0;
      for(ll i = k; i <= 1e5; i += k) { ans += W.count(l, r, i); }
      cout << ans << "\n";
    }
  }
}

yukicoder

結果

テストケース

ソースコード