test/aoj/1549.WM.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/UOA/UAPC/1549

Depends on

• Wavelet行列 (Wavelet Matrix) (src/DataStructure/WaveletMatrix.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/UOA/UAPC/1549
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/DataStructure/WaveletMatrix.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 WaveletMatrix wm(a);
 int Q;
 cin >> Q;
 while (Q--) {
  int l, r, d;
  cin >> l >> r >> d, r++;
  int cnt= wm.count(l, r, d);
  if (cnt == 0) cout << wm.kth_smallest(l, r, 0) - d << '\n';
  else if (cnt == r - l) {
   cout << d - wm.kth_largest(l, r, 0) << '\n';
  } else {
   cout << min(wm.kth_smallest(l, r, cnt) - d, d - wm.kth_smallest(l, r, cnt - 1)) << '\n';
  }
 }
 return 0;
}

#line 1 "test/aoj/1549.WM.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/UOA/UAPC/1549
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/DataStructure/WaveletMatrix.hpp"
#include <algorithm>
#include <array>
#include <cassert>
template <class T> class WaveletMatrix {
 struct SuccinctIndexableDictionary {
  int len, blocks, zeros= 0;
  std::vector<unsigned> bit, sum;
  SuccinctIndexableDictionary(int len): len(len), blocks((len >> 5) + 1), bit(blocks, 0), sum(blocks, 0) {}
  void set(int k) { bit[k >> 5]|= 1U << (k & 31); }
  void build() {
   for (int i= 1; i < blocks; ++i) sum[i]= sum[i - 1] + __builtin_popcount(bit[i - 1]);
   zeros= rank0(len);
  }
  bool operator[](int k) const { return (bit[k >> 5] >> (k & 31)) & 1; }
  int rank(int k) const { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); }
  int rank0(int k) const { return k - rank(k); }
 };
 int len, lg;
 std::vector<SuccinctIndexableDictionary> mat;
 std::vector<T> vec;
public:
 WaveletMatrix(const std::vector<T> &v): len(v.size()), lg(len ? 32 - __builtin_clz(len) : 1), mat(lg, SuccinctIndexableDictionary(len)), vec(v) {
  std::sort(vec.begin(), vec.end()), vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  std::vector<unsigned> cur(len), nex(len);
  for (int i= len; i--;) cur[i]= std::lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin();
  for (auto h= lg; h--; cur.swap(nex)) {
   for (int i= 0; i < len; ++i)
    if ((cur[i] >> h) & 1) mat[h].set(i);
   mat[h].build();
   std::array it{nex.begin(), nex.begin() + mat[h].zeros};
   for (int i= 0; i < len; ++i) *it[mat[h][i]]++= cur[i];
  }
 }
 // k-th(0-indexed) smallest number in v[l,r)
 T kth_smallest(int l, int r, int k) const {
  assert(k < r - l);
  int ret= 0;
  for (auto h= lg; h--;)
   if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); k >= r0 - l0) k-= r0 - l0, ret|= 1 << h, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0;
   else l= l0, r= r0;
  return vec[ret];
 }
 // k-th(0-indexed) largest number in v[l,r)
 T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - k - 1); }
 // count i s.t. (l <= i < r) && (v[i] < ub)
 int count(int l, int r, T ub) const {
  unsigned x= std::lower_bound(vec.begin(), vec.end(), ub) - vec.begin();
  if (x >= 1u << lg) return r - l;
  if (x == 0) return 0;
  int ret= 0;
  for (auto h= lg; h--;)
   if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); (x >> h) & 1) ret+= r0 - l0, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0;
   else l= l0, r= r0;
  return ret;
 }
 // count i s.t. (l <= i < r) && (lb <= v[i] < ub)
 int count(int l, int r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
};
#line 7 "test/aoj/1549.WM.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 WaveletMatrix wm(a);
 int Q;
 cin >> Q;
 while (Q--) {
  int l, r, d;
  cin >> l >> r >> d, r++;
  int cnt= wm.count(l, r, d);
  if (cnt == 0) cout << wm.kth_smallest(l, r, 0) - d << '\n';
  else if (cnt == r - l) {
   cout << d - wm.kth_largest(l, r, 0) << '\n';
  } else {
   cout << min(wm.kth_smallest(l, r, cnt) - d, d - wm.kth_smallest(l, r, cnt - 1)) << '\n';
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	testcase_00	AC	5 ms	4 MB
g++-13	testcase_01	AC	5 ms	4 MB
g++-13	testcase_02	AC	5 ms	3 MB
g++-13	testcase_03	AC	5 ms	4 MB
g++-13	testcase_04	AC	5 ms	4 MB
g++-13	testcase_05	AC	5 ms	3 MB
g++-13	testcase_06	AC	5 ms	4 MB
g++-13	testcase_07	AC	5 ms	4 MB
g++-13	testcase_08	AC	5 ms	4 MB
g++-13	testcase_09	AC	5 ms	4 MB
g++-13	testcase_10	AC	5 ms	4 MB
g++-13	testcase_11	AC	5 ms	4 MB
g++-13	testcase_12	AC	5 ms	4 MB
g++-13	testcase_13	AC	5 ms	4 MB
g++-13	testcase_14	AC	5 ms	4 MB
g++-13	testcase_15	AC	5 ms	3 MB
g++-13	testcase_16	AC	5 ms	4 MB
g++-13	testcase_17	AC	5 ms	4 MB
g++-13	testcase_18	AC	5 ms	4 MB
g++-13	testcase_19	AC	5 ms	4 MB
g++-13	testcase_20	AC	5 ms	4 MB
g++-13	testcase_21	AC	5 ms	4 MB
g++-13	testcase_22	AC	5 ms	4 MB
g++-13	testcase_23	AC	5 ms	4 MB
g++-13	testcase_24	AC	5 ms	3 MB
g++-13	testcase_25	AC	5 ms	4 MB
g++-13	testcase_26	AC	5 ms	4 MB
g++-13	testcase_27	AC	5 ms	3 MB
g++-13	testcase_28	AC	5 ms	4 MB
g++-13	testcase_29	AC	5 ms	4 MB
g++-13	testcase_30	AC	5 ms	4 MB
g++-13	testcase_31	AC	5 ms	4 MB
g++-13	testcase_32	AC	5 ms	3 MB
g++-13	testcase_33	AC	5 ms	4 MB
g++-13	testcase_34	AC	5 ms	4 MB
g++-13	testcase_35	AC	5 ms	4 MB
g++-13	testcase_36	AC	5 ms	4 MB
g++-13	testcase_37	AC	5 ms	4 MB
g++-13	testcase_38	AC	5 ms	4 MB
g++-13	testcase_39	AC	5 ms	4 MB
g++-13	testcase_40	AC	5 ms	4 MB
g++-13	testcase_41	AC	5 ms	4 MB
g++-13	testcase_42	AC	5 ms	3 MB
g++-13	testcase_43	AC	117 ms	5 MB
g++-13	testcase_44	AC	118 ms	5 MB
g++-13	testcase_45	AC	118 ms	5 MB
g++-13	testcase_46	AC	118 ms	5 MB
g++-13	testcase_47	AC	117 ms	5 MB
g++-13	testcase_48	AC	118 ms	5 MB
g++-13	testcase_49	AC	117 ms	5 MB
g++-13	testcase_50	AC	118 ms	5 MB
g++-13	testcase_51	AC	117 ms	5 MB
g++-13	testcase_52	AC	119 ms	5 MB
g++-13	testcase_53	AC	118 ms	5 MB
g++-13	testcase_54	AC	117 ms	5 MB
g++-13	testcase_55	AC	118 ms	5 MB
g++-13	testcase_56	AC	119 ms	5 MB
g++-13	testcase_57	AC	118 ms	5 MB
g++-13	testcase_58	AC	35 ms	4 MB
g++-13	testcase_59	AC	94 ms	5 MB
g++-13	testcase_60	AC	74 ms	4 MB
g++-13	testcase_61	AC	51 ms	4 MB
g++-13	testcase_62	AC	104 ms	5 MB
g++-13	testcase_63	AC	34 ms	4 MB
g++-13	testcase_64	AC	101 ms	5 MB
g++-13	testcase_65	AC	56 ms	4 MB
g++-13	testcase_66	AC	81 ms	4 MB
g++-13	testcase_67	AC	38 ms	5 MB
g++-13	testcase_68	AC	54 ms	4 MB
g++-13	testcase_69	AC	55 ms	4 MB
g++-13	testcase_70	AC	89 ms	4 MB
g++-13	testcase_71	AC	78 ms	4 MB
g++-13	testcase_72	AC	23 ms	4 MB
g++-13	testcase_73	AC	81 ms	5 MB
clang++-18	testcase_00	AC	6 ms	4 MB
clang++-18	testcase_01	AC	5 ms	4 MB
clang++-18	testcase_02	AC	5 ms	4 MB
clang++-18	testcase_03	AC	5 ms	4 MB
clang++-18	testcase_04	AC	5 ms	4 MB
clang++-18	testcase_05	AC	5 ms	4 MB
clang++-18	testcase_06	AC	5 ms	4 MB
clang++-18	testcase_07	AC	5 ms	4 MB
clang++-18	testcase_08	AC	5 ms	4 MB
clang++-18	testcase_09	AC	5 ms	4 MB
clang++-18	testcase_10	AC	5 ms	4 MB
clang++-18	testcase_11	AC	5 ms	4 MB
clang++-18	testcase_12	AC	5 ms	4 MB
clang++-18	testcase_13	AC	5 ms	4 MB
clang++-18	testcase_14	AC	5 ms	4 MB
clang++-18	testcase_15	AC	5 ms	4 MB
clang++-18	testcase_16	AC	5 ms	4 MB
clang++-18	testcase_17	AC	5 ms	4 MB
clang++-18	testcase_18	AC	5 ms	4 MB
clang++-18	testcase_19	AC	5 ms	4 MB
clang++-18	testcase_20	AC	5 ms	4 MB
clang++-18	testcase_21	AC	5 ms	4 MB
clang++-18	testcase_22	AC	5 ms	4 MB
clang++-18	testcase_23	AC	5 ms	4 MB
clang++-18	testcase_24	AC	5 ms	4 MB
clang++-18	testcase_25	AC	5 ms	4 MB
clang++-18	testcase_26	AC	5 ms	4 MB
clang++-18	testcase_27	AC	5 ms	4 MB
clang++-18	testcase_28	AC	5 ms	4 MB
clang++-18	testcase_29	AC	5 ms	4 MB
clang++-18	testcase_30	AC	5 ms	4 MB
clang++-18	testcase_31	AC	5 ms	4 MB
clang++-18	testcase_32	AC	5 ms	4 MB
clang++-18	testcase_33	AC	5 ms	4 MB
clang++-18	testcase_34	AC	5 ms	4 MB
clang++-18	testcase_35	AC	5 ms	4 MB
clang++-18	testcase_36	AC	5 ms	4 MB
clang++-18	testcase_37	AC	5 ms	4 MB
clang++-18	testcase_38	AC	5 ms	4 MB
clang++-18	testcase_39	AC	5 ms	4 MB
clang++-18	testcase_40	AC	5 ms	4 MB
clang++-18	testcase_41	AC	5 ms	4 MB
clang++-18	testcase_42	AC	5 ms	4 MB
clang++-18	testcase_43	AC	116 ms	5 MB
clang++-18	testcase_44	AC	117 ms	5 MB
clang++-18	testcase_45	AC	118 ms	5 MB
clang++-18	testcase_46	AC	115 ms	5 MB
clang++-18	testcase_47	AC	115 ms	5 MB
clang++-18	testcase_48	AC	117 ms	5 MB
clang++-18	testcase_49	AC	116 ms	5 MB
clang++-18	testcase_50	AC	115 ms	5 MB
clang++-18	testcase_51	AC	115 ms	5 MB
clang++-18	testcase_52	AC	117 ms	5 MB
clang++-18	testcase_53	AC	116 ms	5 MB
clang++-18	testcase_54	AC	115 ms	5 MB
clang++-18	testcase_55	AC	114 ms	5 MB
clang++-18	testcase_56	AC	115 ms	5 MB
clang++-18	testcase_57	AC	115 ms	5 MB
clang++-18	testcase_58	AC	34 ms	4 MB
clang++-18	testcase_59	AC	94 ms	5 MB
clang++-18	testcase_60	AC	71 ms	4 MB
clang++-18	testcase_61	AC	50 ms	4 MB
clang++-18	testcase_62	AC	102 ms	5 MB
clang++-18	testcase_63	AC	33 ms	4 MB
clang++-18	testcase_64	AC	99 ms	5 MB
clang++-18	testcase_65	AC	55 ms	4 MB
clang++-18	testcase_66	AC	79 ms	4 MB
clang++-18	testcase_67	AC	37 ms	5 MB
clang++-18	testcase_68	AC	53 ms	4 MB
clang++-18	testcase_69	AC	54 ms	4 MB
clang++-18	testcase_70	AC	86 ms	4 MB
clang++-18	testcase_71	AC	75 ms	4 MB
clang++-18	testcase_72	AC	22 ms	4 MB
clang++-18	testcase_73	AC	80 ms	5 MB

Back to top page