test/yuki/yuki-no945_ykc_manju.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://yukicoder.me/problems/no/945

Code

#define PROBLEM "https://yukicoder.me/problems/no/945"
#include "include/mtl/dual_sparse_table.hpp"
#include <bits/stdc++.h>
using namespace std;

using P = pair<int,int>;
P f(P a, P b) {return min(a,b);}
constexpr int INF = 1e9;
P e() {return {INF, 3};}
using DST = DualSparseTable<P, f, e>;

int main() {
    int n,m; cin>>n>>m;
    map<char,int> mp;
    mp['Y']=0;
    mp['K']=1;
    mp['C']=2;
    DST dst(n);
    for (int i = 0; i < m; i++) {
        int l,r;
        char t;
        cin>>l>>r>>t;
        l--;
        dst.apply(l, r, {i, mp[t]});
    } 
    dst.build();
    array<int,4> ans{};
    for (int i = 0; i < n; i++) {
        auto [id,t] = dst.get(i);
        ans[t]++;
    }
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}

#line 1 "test/yuki/yuki-no945_ykc_manju.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/945"
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif

namespace bm {

/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
  x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
  x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
  return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
  return std::popcount(x);
#else
  return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
  return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_zero(x);
#else
  return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
  return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_one(x);
#else
  return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
  return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
  return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
  constexpr uint64_t hmask = 0x8080808080808080ull;
  constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
  auto a = x & hmask;
  auto b = x & lmask;
  b = hmask - b;
  b = ~b;
  auto c = (a | b) & hmask;
  c *= 0x0002040810204081ull;
  return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
  uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
  return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
  if (x & 0x80)
    return 8;
  uint64_t p = uint64_t(x) * 0x0101010101010101ull;
  p -= 0x8040201008040201ull;
  p = ~p & 0x8080808080808080ull;
  p = (p >> 7) * 0x0101010101010101ull;
  p >>= 56;
  return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
  assert(x != 0);
  return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
  assert(x != 0);
  return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_zero(x);
#else
  if (x == 0)
    return 64;
  auto i = mssb8(summary(x));
  auto j = mssb8(bextr(x, 8 * i, 8));
  return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
  return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_one(x);
#else
  return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
  return clo(x);
}

inline constexpr unsigned clz8(uint8_t x) {
  return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
  x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
  x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
  x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
  x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
  x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
  x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
  return x;
}

/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::has_single_bit(x);
#else
  return x != 0 && (x & (x - 1)) == 0;
#endif
}

/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::bit_width(x);
#else
  return 64 - clz(x);
#endif
}

/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_ceil(x);
#else
  if (x == 0) return 1;
  return 1ull << bit_width(x - 1);
#endif
}

/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_floor(x);
#else
  if (x == 0) return 0;
  return 1ull << (bit_width(x) - 1);
#endif
}

} // namespace bm
#line 3 "include/mtl/dual_sparse_table.hpp"
#include <vector>
#include <algorithm>
#include <iostream>
template <typename T, T (*op)(T, T), T (*e)()>
class DualSparseTable {
 private:
  size_t size_, log_n_;
  std::vector<std::vector<T>> table_;

 public:
  DualSparseTable(size_t size) :
      size_(size),
      log_n_(63-bm::clz(size)),
      table_(log_n_+1, std::vector<T>(size, e())) {}
  template <typename Iter>
  DualSparseTable(Iter begin, Iter end) :
      DualSparseTable(std::distance(begin, end)) {
    std::copy(begin, end, table_[0].begin());
  }

/***
 * @brief Apply to [l, r)
 * @note Complexity: O(1)
 */
  void apply(size_t l, size_t r, const T& a) {
    if (l>=r) return;
    auto d = 63-bm::clz(r-l);
    table_[d][l] = op(table_[d][l], a);
    table_[d][r-(1ull<<d)] = op(table_[d][r-(1ull<<d)], a);
  }

/***
 * @brief Build the table
 * @note Complexity: O(n log n)
 */
  void build() {
    for (int log_n = (int)log_n_-1; log_n >= 0; log_n--) {
      size_t width = 1ull<<log_n;
      for (size_t i = 0; i < size_-width; i++) {
        table_[log_n][i] = op(table_[log_n][i], table_[log_n+1][i]);
        table_[log_n][i+width] = op(table_[log_n][i+width], table_[log_n+1][i]);
      }
    }
  }

  T get(size_t i) const {
    return table_[0][i];
  }

};
#line 3 "test/yuki/yuki-no945_ykc_manju.test.cpp"
#include <bits/stdc++.h>
using namespace std;

using P = pair<int,int>;
P f(P a, P b) {return min(a,b);}
constexpr int INF = 1e9;
P e() {return {INF, 3};}
using DST = DualSparseTable<P, f, e>;

int main() {
    int n,m; cin>>n>>m;
    map<char,int> mp;
    mp['Y']=0;
    mp['K']=1;
    mp['C']=2;
    DST dst(n);
    for (int i = 0; i < m; i++) {
        int l,r;
        char t;
        cin>>l>>r>>t;
        l--;
        dst.apply(l, r, {i, mp[t]});
    } 
    dst.build();
    array<int,4> ans{};
    for (int i = 0; i < n; i++) {
        auto [id,t] = dst.get(i);
        ans[t]++;
    }
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	0_Sample_01.txt	AC	5 ms	3 MB
g++	0_Sample_02.txt	AC	5 ms	3 MB
g++	1_Small_1.txt	AC	5 ms	3 MB
g++	1_Small_10.txt	AC	5 ms	3 MB
g++	1_Small_11.txt	AC	5 ms	4 MB
g++	1_Small_12.txt	AC	5 ms	4 MB
g++	1_Small_13.txt	AC	5 ms	4 MB
g++	1_Small_14.txt	AC	5 ms	3 MB
g++	1_Small_15.txt	AC	5 ms	3 MB
g++	1_Small_16.txt	AC	5 ms	3 MB
g++	1_Small_17.txt	AC	5 ms	4 MB
g++	1_Small_18.txt	AC	5 ms	4 MB
g++	1_Small_19.txt	AC	5 ms	3 MB
g++	1_Small_2.txt	AC	5 ms	3 MB
g++	1_Small_20.txt	AC	5 ms	3 MB
g++	1_Small_3.txt	AC	5 ms	3 MB
g++	1_Small_4.txt	AC	5 ms	3 MB
g++	1_Small_5.txt	AC	5 ms	4 MB
g++	1_Small_6.txt	AC	5 ms	4 MB
g++	1_Small_7.txt	AC	5 ms	3 MB
g++	1_Small_8.txt	AC	5 ms	3 MB
g++	1_Small_9.txt	AC	5 ms	4 MB
g++	2_Small_1.txt	AC	5 ms	4 MB
g++	2_Small_2.txt	AC	5 ms	4 MB
g++	2_Small_3.txt	AC	6 ms	4 MB
g++	2_Small_4.txt	AC	6 ms	4 MB
g++	2_Small_5.txt	AC	5 ms	3 MB
g++	3_Small_1.txt	AC	5 ms	4 MB
g++	3_Small_2.txt	AC	5 ms	4 MB
g++	4_Small_1.txt	AC	5 ms	3 MB
g++	4_Small_2.txt	AC	5 ms	3 MB
g++	5_Large_1.txt	AC	13 ms	8 MB
g++	5_Large_10.txt	AC	35 ms	26 MB
g++	5_Large_11.txt	AC	21 ms	18 MB
g++	5_Large_12.txt	AC	94 ms	17 MB
g++	5_Large_13.txt	AC	62 ms	4 MB
g++	5_Large_14.txt	AC	87 ms	25 MB
g++	5_Large_15.txt	AC	99 ms	13 MB
g++	5_Large_16.txt	AC	15 ms	13 MB
g++	5_Large_17.txt	AC	71 ms	18 MB
g++	5_Large_18.txt	AC	18 ms	5 MB
g++	5_Large_19.txt	AC	39 ms	18 MB
g++	5_Large_2.txt	AC	21 ms	20 MB
g++	5_Large_20.txt	AC	105 ms	15 MB
g++	5_Large_3.txt	AC	45 ms	24 MB
g++	5_Large_4.txt	AC	69 ms	16 MB
g++	5_Large_5.txt	AC	113 ms	30 MB
g++	5_Large_6.txt	AC	71 ms	5 MB
g++	5_Large_7.txt	AC	67 ms	6 MB
g++	5_Large_8.txt	AC	66 ms	9 MB
g++	5_Large_9.txt	AC	29 ms	16 MB
g++	6_Large_1.txt	AC	130 ms	33 MB
g++	6_Large_2.txt	AC	130 ms	33 MB
g++	6_Large_3.txt	AC	130 ms	33 MB
g++	6_Large_4.txt	AC	130 ms	33 MB
g++	6_Large_5.txt	AC	133 ms	33 MB
g++	7_Large_1.txt	AC	30 ms	33 MB
g++	7_Large_2.txt	AC	29 ms	33 MB
g++	8_Large_1.txt	AC	100 ms	33 MB
g++	8_Large_10.txt	AC	84 ms	33 MB
g++	8_Large_11.txt	AC	62 ms	33 MB
g++	8_Large_12.txt	AC	41 ms	33 MB
g++	8_Large_13.txt	AC	43 ms	33 MB
g++	8_Large_14.txt	AC	43 ms	33 MB
g++	8_Large_15.txt	AC	73 ms	33 MB
g++	8_Large_16.txt	AC	112 ms	33 MB
g++	8_Large_2.txt	AC	114 ms	33 MB
g++	8_Large_3.txt	AC	61 ms	33 MB
g++	8_Large_4.txt	AC	104 ms	33 MB
g++	8_Large_5.txt	AC	102 ms	33 MB
g++	8_Large_6.txt	AC	31 ms	33 MB
g++	8_Large_7.txt	AC	64 ms	33 MB
g++	8_Large_8.txt	AC	58 ms	33 MB
g++	8_Large_9.txt	AC	56 ms	33 MB
clang++	0_Sample_01.txt	AC	6 ms	3 MB
clang++	0_Sample_02.txt	AC	5 ms	3 MB
clang++	1_Small_1.txt	AC	5 ms	3 MB
clang++	1_Small_10.txt	AC	5 ms	3 MB
clang++	1_Small_11.txt	AC	5 ms	4 MB
clang++	1_Small_12.txt	AC	6 ms	4 MB
clang++	1_Small_13.txt	AC	5 ms	4 MB
clang++	1_Small_14.txt	AC	5 ms	3 MB
clang++	1_Small_15.txt	AC	5 ms	3 MB
clang++	1_Small_16.txt	AC	5 ms	3 MB
clang++	1_Small_17.txt	AC	5 ms	4 MB
clang++	1_Small_18.txt	AC	5 ms	3 MB
clang++	1_Small_19.txt	AC	5 ms	3 MB
clang++	1_Small_2.txt	AC	5 ms	4 MB
clang++	1_Small_20.txt	AC	5 ms	3 MB
clang++	1_Small_3.txt	AC	5 ms	3 MB
clang++	1_Small_4.txt	AC	5 ms	4 MB
clang++	1_Small_5.txt	AC	5 ms	4 MB
clang++	1_Small_6.txt	AC	5 ms	4 MB
clang++	1_Small_7.txt	AC	5 ms	3 MB
clang++	1_Small_8.txt	AC	5 ms	3 MB
clang++	1_Small_9.txt	AC	5 ms	4 MB
clang++	2_Small_1.txt	AC	5 ms	4 MB
clang++	2_Small_2.txt	AC	6 ms	4 MB
clang++	2_Small_3.txt	AC	6 ms	4 MB
clang++	2_Small_4.txt	AC	6 ms	4 MB
clang++	2_Small_5.txt	AC	6 ms	4 MB
clang++	3_Small_1.txt	AC	5 ms	4 MB
clang++	3_Small_2.txt	AC	5 ms	4 MB
clang++	4_Small_1.txt	AC	5 ms	3 MB
clang++	4_Small_2.txt	AC	5 ms	3 MB
clang++	5_Large_1.txt	AC	13 ms	8 MB
clang++	5_Large_10.txt	AC	32 ms	26 MB
clang++	5_Large_11.txt	AC	20 ms	18 MB
clang++	5_Large_12.txt	AC	90 ms	16 MB
clang++	5_Large_13.txt	AC	62 ms	4 MB
clang++	5_Large_14.txt	AC	83 ms	25 MB
clang++	5_Large_15.txt	AC	96 ms	13 MB
clang++	5_Large_16.txt	AC	14 ms	13 MB
clang++	5_Large_17.txt	AC	65 ms	18 MB
clang++	5_Large_18.txt	AC	18 ms	5 MB
clang++	5_Large_19.txt	AC	36 ms	18 MB
clang++	5_Large_2.txt	AC	20 ms	20 MB
clang++	5_Large_20.txt	AC	101 ms	15 MB
clang++	5_Large_3.txt	AC	41 ms	24 MB
clang++	5_Large_4.txt	AC	65 ms	16 MB
clang++	5_Large_5.txt	AC	105 ms	30 MB
clang++	5_Large_6.txt	AC	70 ms	5 MB
clang++	5_Large_7.txt	AC	68 ms	6 MB
clang++	5_Large_8.txt	AC	65 ms	9 MB
clang++	5_Large_9.txt	AC	27 ms	16 MB
clang++	6_Large_1.txt	AC	127 ms	33 MB
clang++	6_Large_2.txt	AC	126 ms	33 MB
clang++	6_Large_3.txt	AC	125 ms	33 MB
clang++	6_Large_4.txt	AC	125 ms	33 MB
clang++	6_Large_5.txt	AC	130 ms	33 MB
clang++	7_Large_1.txt	AC	26 ms	33 MB
clang++	7_Large_2.txt	AC	26 ms	33 MB
clang++	8_Large_1.txt	AC	95 ms	33 MB
clang++	8_Large_10.txt	AC	79 ms	33 MB
clang++	8_Large_11.txt	AC	59 ms	33 MB
clang++	8_Large_12.txt	AC	36 ms	33 MB
clang++	8_Large_13.txt	AC	39 ms	33 MB
clang++	8_Large_14.txt	AC	40 ms	33 MB
clang++	8_Large_15.txt	AC	67 ms	33 MB
clang++	8_Large_16.txt	AC	107 ms	33 MB
clang++	8_Large_2.txt	AC	109 ms	33 MB
clang++	8_Large_3.txt	AC	57 ms	33 MB
clang++	8_Large_4.txt	AC	98 ms	33 MB
clang++	8_Large_5.txt	AC	96 ms	33 MB
clang++	8_Large_6.txt	AC	27 ms	33 MB
clang++	8_Large_7.txt	AC	59 ms	33 MB
clang++	8_Large_8.txt	AC	54 ms	33 MB
clang++	8_Large_9.txt	AC	51 ms	33 MB

Back to top page