Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: test/yukicoder/1371.WM.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1371
// 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], --A[i];
 if (A[0] < A[1])
  for (auto &x: A) x= N - 1 - x;
 vector<int> B(N);
 for (int i= 0; i < N; ++i) {
  if (i & 1) {
   B[i]= A[i - 1];
   if (i + 1 < N) B[i]= min(B[i], A[i + 1]);
  } else {
   B[i]= 0;
   if (i) B[i]= max(B[i], A[i - 1]);
   if (i + 1 < N) B[i]= max(B[i], A[i + 1]);
  }
 }
 vector<int> ve(N, -1), vo(N, -1);
 for (int i= 0; i < N; ++i) {
  if (i & 1) vo[A[i]]= B[i];
  else ve[A[i]]= B[i];
 }
 WaveletMatrix<int> wme(ve), wmo(vo);
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  if (i & 1) {
   ans+= wme.count(0, B[i], 0, A[i]);
   ans+= wmo.count(0, B[i], A[i] + 1, N);
  } else {
   ans+= wme.count(B[i] + 1, N, 0, A[i]);
   ans+= wmo.count(B[i] + 1, N, A[i] + 1, N);
  }
 }
 ans= (ans - N) / 2;
 cout << ans << '\n';
 return 0;
}
#line 1 "test/yukicoder/1371.WM.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1371
// 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/yukicoder/1371.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], --A[i];
 if (A[0] < A[1])
  for (auto &x: A) x= N - 1 - x;
 vector<int> B(N);
 for (int i= 0; i < N; ++i) {
  if (i & 1) {
   B[i]= A[i - 1];
   if (i + 1 < N) B[i]= min(B[i], A[i + 1]);
  } else {
   B[i]= 0;
   if (i) B[i]= max(B[i], A[i - 1]);
   if (i + 1 < N) B[i]= max(B[i], A[i + 1]);
  }
 }
 vector<int> ve(N, -1), vo(N, -1);
 for (int i= 0; i < N; ++i) {
  if (i & 1) vo[A[i]]= B[i];
  else ve[A[i]]= B[i];
 }
 WaveletMatrix<int> wme(ve), wmo(vo);
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  if (i & 1) {
   ans+= wme.count(0, B[i], 0, A[i]);
   ans+= wmo.count(0, B[i], A[i] + 1, N);
  } else {
   ans+= wme.count(B[i] + 1, N, 0, A[i]);
   ans+= wmo.count(B[i] + 1, N, A[i] + 1, N);
  }
 }
 ans= (ans - N) / 2;
 cout << ans << '\n';
 return 0;
}

Test cases

Env Name Status Elapsed Memory
g++-13 0sample1.txt :heavy_check_mark: AC 6 ms 4 MB
g++-13 0sample2.txt :heavy_check_mark: AC 6 ms 4 MB
g++-13 0sample3.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 1s1.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 1s2.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 1s3.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 1s4.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 1s5.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 3m1.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 3m3.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 3m5.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 3m6.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 3m7.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 5r1.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 5r2.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 5r3.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 5r4.txt :heavy_check_mark: AC 5 ms 4 MB
g++-13 5r5.txt :heavy_check_mark: AC 5 ms 3 MB
g++-13 6l1.txt :heavy_check_mark: AC 155 ms 11 MB
g++-13 6l3.txt :heavy_check_mark: AC 155 ms 11 MB
g++-13 6l5.txt :heavy_check_mark: AC 161 ms 11 MB
g++-13 6l6.txt :heavy_check_mark: AC 152 ms 11 MB
g++-13 6l7.txt :heavy_check_mark: AC 153 ms 11 MB
g++-13 9r1.txt :heavy_check_mark: AC 283 ms 11 MB
g++-13 9r10.txt :heavy_check_mark: AC 283 ms 11 MB
g++-13 9r2.txt :heavy_check_mark: AC 282 ms 11 MB
g++-13 9r3.txt :heavy_check_mark: AC 286 ms 11 MB
g++-13 9r4.txt :heavy_check_mark: AC 287 ms 11 MB
g++-13 9r5.txt :heavy_check_mark: AC 285 ms 11 MB
g++-13 9r7.txt :heavy_check_mark: AC 286 ms 11 MB
g++-13 9r8.txt :heavy_check_mark: AC 283 ms 11 MB
g++-13 9r9.txt :heavy_check_mark: AC 285 ms 11 MB
clang++-18 0sample1.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 0sample2.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 0sample3.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 1s1.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 1s2.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 1s3.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 1s4.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 1s5.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 3m1.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 3m3.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 3m5.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 3m6.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 3m7.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 5r1.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 5r2.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 5r3.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 5r4.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 5r5.txt :heavy_check_mark: AC 5 ms 4 MB
clang++-18 6l1.txt :heavy_check_mark: AC 153 ms 11 MB
clang++-18 6l3.txt :heavy_check_mark: AC 153 ms 11 MB
clang++-18 6l5.txt :heavy_check_mark: AC 163 ms 11 MB
clang++-18 6l6.txt :heavy_check_mark: AC 156 ms 11 MB
clang++-18 6l7.txt :heavy_check_mark: AC 157 ms 11 MB
clang++-18 9r1.txt :heavy_check_mark: AC 283 ms 11 MB
clang++-18 9r10.txt :heavy_check_mark: AC 285 ms 11 MB
clang++-18 9r2.txt :heavy_check_mark: AC 283 ms 11 MB
clang++-18 9r3.txt :heavy_check_mark: AC 283 ms 11 MB
clang++-18 9r4.txt :heavy_check_mark: AC 284 ms 11 MB
clang++-18 9r5.txt :heavy_check_mark: AC 284 ms 11 MB
clang++-18 9r7.txt :heavy_check_mark: AC 286 ms 11 MB
clang++-18 9r8.txt :heavy_check_mark: AC 283 ms 11 MB
clang++-18 9r9.txt :heavy_check_mark: AC 285 ms 11 MB
Back to top page