結果

問題 No.1371 交換門松列・松
ユーザー hashiryohashiryo
提出日時 2023-10-30 12:49:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 460 ms / 4,000 ms
コード長 4,316 bytes
コンパイル時間 2,673 ms
コンパイル使用メモリ 217,148 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2023-10-30 12:49:53
合計ジャッジ時間 10,577 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 287 ms
11,392 KB
testcase_19 AC 277 ms
11,392 KB
testcase_20 AC 293 ms
11,392 KB
testcase_21 AC 297 ms
11,392 KB
testcase_22 AC 282 ms
11,392 KB
testcase_23 AC 434 ms
11,392 KB
testcase_24 AC 435 ms
11,392 KB
testcase_25 AC 447 ms
11,392 KB
testcase_26 AC 433 ms
11,392 KB
testcase_27 AC 460 ms
11,392 KB
testcase_28 AC 433 ms
11,392 KB
testcase_29 AC 429 ms
11,392 KB
testcase_30 AC 458 ms
11,392 KB
testcase_31 AC 431 ms
11,392 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= long long> class WaveletMatrix {
 struct SuccinctIndexableDictionary {
  std::size_t len, blocks, zeros;
  std::vector<unsigned> bit, sum;
  SuccinctIndexableDictionary()= default;
  SuccinctIndexableDictionary(std::size_t 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 (std::size_t 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; }
  std::size_t rank(std::size_t k) const { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); }
  std::size_t rank0(std::size_t k) const { return k - rank(k); }
 };
 std::size_t len, lg;
 std::vector<SuccinctIndexableDictionary> mat;
 std::vector<T> vec;
public:
 WaveletMatrix()= default;
 WaveletMatrix(const std::vector<T> &v): len(v.size()), lg(32 - __builtin_clz(std::max<int>(len, 1))), mat(lg, 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 (std::size_t 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 (std::size_t 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);
  std::size_t 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)
 std::size_t count(int l, int r, T ub) const {
  std::size_t x= std::lower_bound(vec.begin(), vec.end(), ub) - vec.begin();
  if (x >= 1u << lg) return r - l;
  if (x == 0) return 0;
  std::size_t 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)
 std::size_t count(int l, int r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
};
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]);
  }
 }
 debug(A, B);
 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;
}
0