結果
| 問題 | No.924 紲星 |
| ユーザー |
 kyawa
|
| 提出日時 | 2021-12-17 18:48:33 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,036 ms / 4,000 ms |
| コード長 | 5,903 bytes |
| コンパイル時間 | 3,294 ms |
| コンパイル使用メモリ | 240,016 KB |
| 実行使用メモリ | 71,296 KB |
| 最終ジャッジ日時 | 2023-10-12 21:55:45 |
| 合計ジャッジ時間 | 14,025 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,352 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 1 ms
4,348 KB |
| testcase_03 | AC | 3 ms
4,348 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 4 ms
4,352 KB |
| testcase_06 | AC | 3 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,352 KB |
| testcase_08 | AC | 1,036 ms
70,928 KB |
| testcase_09 | AC | 1,018 ms
71,100 KB |
| testcase_10 | AC | 1,001 ms
71,296 KB |
| testcase_11 | AC | 1,002 ms
70,972 KB |
| testcase_12 | AC | 1,004 ms
71,252 KB |
| testcase_13 | AC | 405 ms
29,540 KB |
| testcase_14 | AC | 339 ms
22,236 KB |
| testcase_15 | AC | 346 ms
25,272 KB |
| testcase_16 | AC | 549 ms
57,060 KB |
| testcase_17 | AC | 548 ms
33,068 KB |
| testcase_18 | AC | 1 ms
4,348 KB |
ソースコード
#include<bits/stdc++.h>
using namespace std;
class WaveletMatrix{
public:
long bitsize;
vector<long> table_origin;
vector<long> table_sorted;
WaveletMatrix(vector<long> table) : table_origin(table){
long table_max = *max_element(table.begin(), table.end());
tablesize = table.size();
bitsize = 0;
while(table_max){
bitsize++;
table_max >>= 1;
}
assert(bitsize);
matrix.resize(bitsize, vector<bool>(tablesize));
zero_count.resize(bitsize, vector<long>(tablesize + 1, 0));
for(long i = 0; i < bitsize; i++){
for(long j = 0; j < tablesize; j++){
matrix[i][j] = (table[j] >> (bitsize - i - 1)) & 1;
if(not matrix[i][j]) zero_count[i][j + 1]++;
zero_count[i][j + 1] += zero_count[i][j];
}
stable_sort(table.begin(), table.end(), [&](auto a, auto b){return ((a >> (bitsize - i - 1)) & 1) < ((b >> (bitsize - i - 1)) & 1);});
}
table_sorted = table;
}
long rank(long r, long x){
//count x in [0, r)
long L = 0; long R = r;//たぶんここLをlとして、引数にできる
for(long level = 0; level < bitsize; level++){
long same;//matrix[level][L, R)の中に、(x>>(bitsize-level-1)&1 と一致するのはいくつあるか?
bool x_at_level = (x >> (bitsize - level - 1) & 1);
if(x_at_level == 0){
same = zero_count[level][R] - zero_count[level][L];
L = zero_count[level][L]; R = L + same;
}else{
same = (R - zero_count[level][R]) - (L - zero_count[level][L]);
L = zero_count[level][tablesize] + (L - zero_count[level][L]); R = L + same;
}
}
return R - L;
}
long kth_min(long l, long r, long k/*0-indexed*/){
long L = l; long R = r;
for(long level = 0; level < bitsize; level++){
auto [Lcount0, Lcount1] = counts(0, L, level);
auto [count0, count1] = counts(L, R, level);
if(k < count0){
L = Lcount0;
R = L + count0;
}else{
L = zero_count[level][tablesize] + Lcount1;
R = L + count1;
k -= count0;
}
}
return table_sorted[L];
}
long range_freq(long l, long r, long lower, long upper){
//count i s.t. l <= i < r and lower <= table[i] < upper
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
private:
vector<vector<bool>> matrix;
vector<vector<long>> zero_count;//count 0 in matrix[i][0, r)
long tablesize;
pair<long,long> counts(long l, long r, long level){
//{0の個数, 1の個数} in matrix[level][l, r)を返す
return {zero_count[level][r] - zero_count[level][l], (r - zero_count[level][r]) - (l - zero_count[level][l])};
}
long range_freq(long l, long r, long upper){
//count i s.t. l <= i < r and table[i] < upper
if(upper >= (1 << bitsize)) return r - l;
if(upper < 0) return 0;
long res = 0;
long L = l; long R = r;
for(long level = 0; level < bitsize; level++){
auto [Lcount0, Lcount1] = counts(0, L, level);
auto [count0, count1] = counts(L, R, level);
if(((upper >> (bitsize - level - 1)) & 1) == 0){
//matrix[level][i] = 1 なら 必ず upper < table[i]
L = Lcount0;
R = L + count0;
}else{
//matrix[level][i] = 0 なら 必ず table[i] < upper
res += count0;
L = zero_count[level][tablesize] + Lcount1;
R = L + count1;
}
}
return res;
}
};
class FenwickTree{
public:
vector<long> table;
long siz;
FenwickTree(long siz) : table(siz + 1), siz(siz) {}
long sum(long index){
long res = 0;
index++;//0-indexed to 1-indexed
while(index > 0){
res += table[index];
index -= (index & -index);
}
return res;
}
void add(long index, long value){
index++;//0-indexed to 1-indexed
while(index < siz + 1){
table[index] += value;
index += (index & -index);
}
}
};
int main(){
long N, Q; cin >> N >> Q;
vector<long> A(N);
for(long i = 0; i < N; i++) {
cin >> A[i]; A[i] += 1000000000;
}
vector<long> acc(N + 1, 0);
for(long i = 0; i < N; i++) acc[i+1] = acc[i] + A[i];
WaveletMatrix wm(A);
vector<tuple<long,long,long,long>> query(Q);
vector<long> res(Q);
for(long i = 0; i < Q; i++){
long l, r, mid;
cin >> l >> r; l--; r--;
mid = wm.kth_min(l, r+1, (r-l)/2);
query[i] = {mid, l, r, i};
}
sort(query.begin(), query.end());
vector<pair<long,long>> AandI(N);
for(long i = 0; i < N; i++) AandI[i] = {A[i], i};
sort(AandI.begin(), AandI.end());
long q = 0;
FenwickTree bit(N);
for(long j = 0; j < N; j++){
auto [a, i] = AandI[j];
while(q < Q and tuple<long,long,long,long>({a,0,0,0}) <= query[q] and query[q] <= tuple<long,long,long,long>({a,LONG_MAX,LONG_MAX,LONG_MAX})){
auto [mid, l, r, res_i] = query[q];
long sumoflessthanmid = bit.sum(r) - bit.sum(l-1);
long sumofgreaterthanmid = acc[r+1] - acc[l] - mid - sumoflessthanmid;
long cntoflessthanmid = (r - l) / 2;
long cntofgreaterthanmid = r - l - cntoflessthanmid;
res[res_i] = (mid * cntoflessthanmid - sumoflessthanmid) + (sumofgreaterthanmid - mid * cntofgreaterthanmid);
q++;
}
bit.add(i, a);
}
for(long i = 0; i < Q; i++) cout << res[i] << '\n';
}