提出 #22841414
ソースコード 拡げる
#define _USE_MATH_DEFINES
#pragma GCC target ("popcnt,bmi2,fma,fma4,avx2")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<(a);i++)
#define repft(i,a,b) for(int i=(a);i<(b);i++)
template <typename IdxType = uint32_t, int WORD_SIZE = 64>
struct bit_vector {
static constexpr uint32_t wsize = WORD_SIZE;
static_assert(WORD_SIZE == 32 || WORD_SIZE == 64);
using WordT = typename conditional<WORD_SIZE == 64, uint64_t, uint32_t>::type;
#if _MSC_VER >= 1920 || __INTEL_COMPILER
inline static int bitCount32(uint32_t bits) {
return (int)_mm_popcnt_u32(bits);
}
inline static int bitCount64(uint64_t bits) {
return (int)_mm_popcnt_u64(bits);
}
#else
inline static int bitCount32(uint32_t bits) {
return __builtin_popcount(bits);
}
inline static int bitCount64(uint64_t bits) {
return __builtin_popcountll(bits);
}
#endif
inline static uint32_t rank(const uint32_t x, const uint32_t i) {
//return bitCount32((uint32_t)_bzhi_u32(x, i));
return bitCount32(x & ((1u << i) - 1));
}
inline static uint32_t rank(const uint64_t x, const uint32_t i) {
//return bitCount64((uint64_t)_bzhi_u64(x, i));
return bitCount64(x & ((1ull << i) - 1));
}
#pragma pack(4)
struct block_t {
WordT nbit;
IdxType nsum;
};
#pragma pack()
IdxType zeros, n;
vector<block_t> block;
bit_vector(const IdxType _n = 0) : n(_n), block(n / wsize + 1) {}
inline bool is_zero(const IdxType i) const {
return (block[i / wsize].nbit >> (i % wsize)) & 1;
}
inline void nset(const IdxType i) {
block[i / wsize].nbit |= (WordT)1 << (i % wsize);
}
inline void nset_block_bit(const IdxType i, const WordT val) {
block[i].nbit = val;
}
inline WordT get_block_nbit(const IdxType i) const {
return block[i].nbit;
}
void build() {
for (IdxType j = 0; j < n / wsize; ++j) {
block[j + 1].nsum = block[j].nsum + bitCount64(block[j].nbit);
}
zeros = rank0(n);
}
inline IdxType rank0(const IdxType i) const {
auto&& e = block[i / wsize];
return e.nsum + rank(e.nbit, i % wsize);
}
inline IdxType rank1(const IdxType i) const {
return i - rank0(i);
}
};
template <class T = uint64_t, typename IdxType = uint32_t, int WORD_SIZE = 64>
struct WaveletMatrix {
static constexpr uint32_t wsize = WORD_SIZE;
using WordT = typename bit_vector<IdxType, WORD_SIZE>::WordT;
IdxType size, bit_len;
vector<T> a;
vector<bit_vector<IdxType, WORD_SIZE>> bv;
WaveletMatrix(IdxType _n = 0) {
reset(_n);
}
void reset(IdxType _n = 0) {
size = (_n + wsize - 1) & (~(wsize - 1));
a.resize(size);
for (IdxType i = _n; i < size; ++i) {
a[i] = 0;
}
}
void resize(IdxType _n) {
size = (_n + wsize - 1) & (~(wsize - 1));
a.resize(size);
}
static constexpr int get_bit_len(uint64_t val) {
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
val |= val >> 16;
val |= val >> 32;
return bit_vector<>::bitCount64(val);
}
inline void set_prebuild(const IdxType i, const T& val) {
a[i] = val;
}
void build(const IdxType data_bit) {
bit_len = data_bit;
bv.assign(bit_len, size);
vector<T> nxt(size);
T mask = ((T)1 << bit_len) - 1;
const IdxType n_dw = size / wsize;
for (IdxType h = bit_len; h--; ) {
mask >>= 1;
T* it = &a[0];
for (IdxType i = 0; i < n_dw; ++i, it += wsize) {
WordT bits = 0;
for (int j = 0; j < wsize; ++j) {
if (it[j] <= mask) { // 0
bits |= ((WordT)1 << j);
}
}
bv[h].nset_block_bit(i, bits);
}
bv[h].build();
auto its = array{
begin(nxt),
begin(nxt) + bv[h].zeros
};
for (IdxType i = 0; i < size; ++i) {
const T v = a[i];
*(its[v > mask]++) = v & mask;
}
swap(a, nxt);
}
a.clear();
a.shrink_to_fit();
}
T kth(IdxType l, IdxType r, IdxType k) const {
T res = 0;
for (int h = bit_len; h--; ) {
const IdxType l0 = bv[h].rank0(l);
const IdxType r0 = bv[h].rank0(r);
const IdxType d0 = r0 - l0;
if (k < d0) {
l = l0;
r = r0;
} else {
k -= d0;
res |= (T)1 << h;
l += bv[h].zeros - l0;
r += bv[h].zeros - r0;
}
}
return res;
}
// [l, r) に含まれる [a, b) の範囲の値の個数 O(log(max))
int range_freq(const IdxType l, const IdxType r, const T a, const T b) const {
//return less_freq(l, r, b) - less_freq(l, r, a);
if (l >= r) return 0;
IdxType la = l, lb = l;
IdxType ra = r, rb = r;
IdxType res = 0;
for (IdxType d = bit_len; d--; ) {
const IdxType la0 = bv[d].rank0(la);
const IdxType lb0 = bv[d].rank0(lb);
const IdxType ra0 = bv[d].rank0(ra);
const IdxType rb0 = bv[d].rank0(rb);
if (((a >> d) & 1) == 0) {
la = la0;
ra = ra0;
} else {
res -= ra0 - la0;
la += bv[d].zeros - la0;
ra += bv[d].zeros - ra0;
}
if (((b >> d) & 1) == 0) {
lb = lb0;
rb = rb0;
} else {
res += rb0 - lb0;
lb += bv[d].zeros - lb0;
rb += bv[d].zeros - rb0;
}
}
return res;
}
};
vector<int> G[200005];
vector<int> z;
vector<int> w;
WaveletMatrix<uint32_t> wm;
void dfs(int i, int d) {
int x = z.size();
w[i] = x;
wm.set_prebuild(x, d);
z.push_back(0);
for(int j : G[i]) {
dfs(j, d + 1);
}
z[x] = z.size();
}
void solve(int n, std::vector<int> p, int q, std::vector<int> u, std::vector<int> d){
w.resize(n);
wm.resize(n);
repft(i, 1, n) {
int a = p[i-1]-1;
G[a].push_back(i);
}
dfs(0, 0);
wm.build(18);
rep(i, q) {
--u[i];
int r = wm.range_freq(w[u[i]], z[w[u[i]]], d[i], d[i] + 1);
printf("%d\n", r);
}
}
// ~/.local/lib/python3.6/site-packages/atcodertools/tools/templates/default_template.cpp
// Generated by 2.3.0 https://github.com/kyuridenamida/atcoder-tools (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
int N;
scanf("%d", &N);
std::vector<int> P(N-2+1);
for(int i = 0 ; i < N-2+1 ; i++){
scanf("%d", &P[i]);
}
int Q;
scanf("%d", &Q);
std::vector<int> U(Q);
std::vector<int> D(Q);
for(int i = 0 ; i < Q ; i++){
scanf("%d", &U[i]);
scanf("%d", &D[i]);
}
solve(N, std::move(P), Q, std::move(U), std::move(D));
return 0;
}
提出情報
コンパイルエラー
./Main.cpp: In instantiation of ‘void WaveletMatrix<T, IdxType, WORD_SIZE>::build(IdxType) [with T = unsigned int; IdxType = unsigned int; int WORD_SIZE = 64]’:
./Main.cpp:222:16: required from here
./Main.cpp:121:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const uint32_t’ {aka ‘const unsigned int’} [-Wsign-compare]
121 | for (int j = 0; j < wsize; ++j) {
| ~~^~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:235:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
235 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
./Main.cpp:238:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
238 | scanf("%d", &P[i]);
| ~~~~~^~~~~~~~~~~~~
./Main.cpp:241:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
241 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
./Main.cpp:245:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
245 | scanf("%d", &U[i]);
| ~~~~~^~~~~~~~~~~~~
./Main.cpp:246:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
246 | scanf("%d", &D[i]);
| ~~~~~^~~~~~~~~~~~~
ジャッジ結果
| セット名 |
Sample |
All |
| 得点 / 配点 |
0 / 0 |
500 / 500 |
| 結果 |
|
|
| セット名 |
テストケース |
| Sample |
sample_00 |
| All |
binary_00, binary_01, binary_02, binary_03, binary_04, binary_05, binary_06, binary_07, binary_08, binary_09, bound_00, bound_01, bound_02, bound_03, broomlike_00, broomlike_01, broomlike_02, broomlike_03, broomlike_04, random_00, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, sample_00 |
| ケース名 |
結果 |
実行時間 |
メモリ |
| binary_00 |
AC |
100 ms |
14468 KiB |
| binary_01 |
AC |
93 ms |
12672 KiB |
| binary_02 |
AC |
82 ms |
13896 KiB |
| binary_03 |
AC |
61 ms |
13744 KiB |
| binary_04 |
AC |
96 ms |
14384 KiB |
| binary_05 |
AC |
61 ms |
12680 KiB |
| binary_06 |
AC |
50 ms |
13160 KiB |
| binary_07 |
AC |
36 ms |
10332 KiB |
| binary_08 |
AC |
78 ms |
13352 KiB |
| binary_09 |
AC |
128 ms |
16664 KiB |
| bound_00 |
AC |
153 ms |
35792 KiB |
| bound_01 |
AC |
154 ms |
35860 KiB |
| bound_02 |
AC |
71 ms |
9564 KiB |
| bound_03 |
AC |
74 ms |
9484 KiB |
| broomlike_00 |
AC |
106 ms |
22260 KiB |
| broomlike_01 |
AC |
102 ms |
23724 KiB |
| broomlike_02 |
AC |
125 ms |
23392 KiB |
| broomlike_03 |
AC |
114 ms |
19404 KiB |
| broomlike_04 |
AC |
103 ms |
23508 KiB |
| random_00 |
AC |
43 ms |
10940 KiB |
| random_01 |
AC |
108 ms |
15520 KiB |
| random_02 |
AC |
76 ms |
10280 KiB |
| random_03 |
AC |
103 ms |
11812 KiB |
| random_04 |
AC |
136 ms |
16376 KiB |
| random_05 |
AC |
49 ms |
9112 KiB |
| random_06 |
AC |
121 ms |
14432 KiB |
| random_07 |
AC |
123 ms |
13832 KiB |
| random_08 |
AC |
72 ms |
14604 KiB |
| random_09 |
AC |
117 ms |
16020 KiB |
| sample_00 |
AC |
12 ms |
8392 KiB |