#869712 (C++17) No.789 範囲の合計

提出ソース

結果

問題	No.789 範囲の合計
ユーザー	tonegawa
提出日時	2023-05-16 06:28:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	9,082 bytes
コンパイル時間	1,536 ms
コンパイル使用メモリ	141,588 KB
実行使用メモリ	8,960 KB
最終ジャッジ日時	2024-05-08 07:13:26
合計ジャッジ時間	3,656 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	RE	-
testcase_03	AC	50 ms 6,944 KB
testcase_04	AC	80 ms 8,448 KB
testcase_05	RE	-
testcase_06	AC	53 ms 7,680 KB
testcase_07	AC	41 ms 6,944 KB
testcase_08	AC	56 ms 8,960 KB
testcase_09	AC	54 ms 8,448 KB
testcase_10	RE	-
testcase_11	AC	47 ms 8,320 KB
testcase_12	AC	43 ms 8,064 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 2 ".lib/data_structure/bit_sequence/bit_operation.hpp"
#include <stdint.h>
#include <vector>

constexpr static uint64_t mask_32_64 = 0xFFFFFFFF00000000;
constexpr static uint64_t mask_0_32  = 0x00000000FFFFFFFF;
constexpr static uint64_t mask_48_64 = 0xFFFF000000000000;
constexpr static uint64_t mask_32_48 = 0x0000FFFF00000000;
constexpr static uint64_t mask_16_32 = 0x00000000FFFF0000;
constexpr static uint64_t mask_0_16  = 0x000000000000FFFF;
constexpr static int TABLE_SIZE_LOG = 16, TABLE_SIZE = 1 << TABLE_SIZE_LOG;

static std::vector<std::vector<int8_t>> select_build(){
  std::vector<std::vector<int8_t>> ret(TABLE_SIZE, std::vector<int8_t>(TABLE_SIZE_LOG, -1));
  for(int i = 0; i < TABLE_SIZE; i++){
    int pcnt = 0;
    for(int j = 0; j < TABLE_SIZE_LOG; j++) if((i >> j) & 1) ret[i][pcnt++] = j;
  }
  return ret;
}
// k-bit目以降(kも含む)に初めて現れる1の位置, 無い場合は-1
static int find_next_32bit(uint32_t x, int k){
  uint32_t b = x >> k;
  if(!b) return -1;
  return k + __builtin_ctz(b);
}
// k-bit目以降(kも含む)に初めて現れる1の位置, 無い場合は-1
static int find_next_64bit(uint64_t x, int k){
  uint64_t b = x >> k;
  if(!b) return -1;
  return k + __builtin_ctzll(b);
}
// 0 <= k <= 63
// k-bit目以前(kも含む)に初めて現れる1の位置, 無い場合は-1
static int find_prev_64bit(uint64_t x, int k){
  uint64_t b = x << (63 - k);
  if(!b) return -1;
  return k - (63 - __builtin_clzll(b));
}
// k番目(0-indexed)の1の場所(0-indexed)を返す. 無い場合壊れる
static int select_32bit(uint32_t x, int k){
  static std::vector<std::vector<int8_t>> table = select_build();
  int r = __builtin_popcount(x & mask_0_16);
  if(r > k) return table[x & mask_0_16][k];
  return 16 + table[(x & mask_16_32) >> 16][k - r];
}
// k番目(0-indexed)の1の場所(0-indexed)を返す. 無い場合壊れる
static int select_64bit(uint64_t x, int k){
  static std::vector<std::vector<int8_t>> table = select_build();
  int r = __builtin_popcount(x & mask_0_32);
  if(r > k){
    int rr = __builtin_popcount(x & mask_0_16);
    if(rr > k) return table[x & mask_0_16][k];
    else return 16 + table[(x & mask_16_32) >> 16][k - rr];
  }else{
    k -= r;
    int lr = __builtin_popcountll(x & mask_32_48);
    if(lr > k) return 32 + table[(x & mask_32_48) >> 32][k];
    else return 48 + table[(x & mask_48_64) >> 48][k - lr];
  }
}
// 先頭k_bit(0 <= k <= 32)の1の数
static int rank_32bit(uint32_t x, int k){
  return k == 32 ? __builtin_popcount(x) : __builtin_popcount(x & ((1ULL << k) - 1));
}
// 先頭k_bit(0 <= k <= 64)の1の数
static int rank_64bit(uint64_t x, int k){
  return k == 64 ? __builtin_popcountll(x) : __builtin_popcountll(x & ((1ULL << k) - 1));
}
#line 4 "sparse_bit.hpp"
#include <cassert>
#include <algorithm>

template<typename Val>
struct sparse_binary_indexed_tree{
private:
  using I = int;
  static constexpr int bitlen = sizeof(I) * 8;
  // idxの2進数においてk-bitから下位bitに向けて1がいくつ続くか
  static int count_consecutive_one(I idx, int k){
    static_assert(bitlen == 32 || bitlen == 64);
    if(bitlen == 32) return __builtin_clz(~((uint32_t)idx << (31 - k)));
    return __builtin_clzll(~((uint64_t)idx << (63 - k)));
  }
  static int count_trailing_one(I idx){
    static_assert(bitlen == 32 || bitlen == 64);
    if(bitlen == 32) return __builtin_ctz(~(uint32_t)idx);
    return __builtin_ctzll(~(uint64_t)idx);
  }
  I maxn;
  int h;
  struct node{
    I idx;
    std::vector<node*> ch;
    Val val, sum;
    I ch_flag;
    node(I idx, Val val): idx(idx), val(val), sum(val){}
    int find_next_ch(int a){
      static_assert(bitlen == 32 || bitlen == 64);
      if(bitlen == 32) return find_next_32bit(ch_flag, a);
      return find_next_64bit(ch_flag, a);
    }
  };
  node *root;
  void update(node* &v, I idx, Val x, int h_cur){
    if(!v){
      v = new node(idx, x);
      return;
    }else if(v->idx == idx){
      v->val += x;
      v->sum += x;
      return;
    }else v->sum += x;
    if(h_cur == -1 || count_trailing_one(idx) == h_cur + 1) return; // 残りの下位bitが全て1なら終了
    int k = count_consecutive_one(idx, h_cur);
    int t = count_consecutive_one(v->idx, h_cur);
    bool f = false;
    if(v->idx > idx){
      if(k || t) f = true;
    }else if(!k && !t) f = true;
    if(f) std::swap(v->idx, idx), std::swap(v->val, x), std::swap(k, t);
    if(v->ch.size() <= k) v->ch.resize(k + 1, nullptr);
    update(v->ch[k], idx, x, h_cur - 1 - k);
    v->ch_flag |= 1ULL << k;
  }
  Val query(node *v, I idx, int h_cur){
    if(!v || h_cur == -1) return Val(0);
    Val res = v->idx < idx ? v->val : Val(0);
    int k = count_consecutive_one(idx, h_cur);
    int maxk = std::min(k, (int)v->ch.size());
    for(int i = v->find_next_ch(0); i < maxk && i != -1; i = v->find_next_ch(i + 1)) res += v->ch[i]->sum;
    if((v->ch_flag >> k) & 1) res += query(v->ch[k], idx, h_cur - 1 - k);
    return res;
  }
public:
  sparse_binary_indexed_tree(): root(nullptr){}
  // [0, n)
  sparse_binary_indexed_tree(I n): root(nullptr){
    n = std::max(n + 1, 2);
    maxn = 1, h = 0;
    while(maxn < n) maxn <<= 1, h++;
  }
  void update(I idx, Val x){
    assert(0 <= idx && idx < maxn);
    update(root, idx, x, h - 1);
  }
  Val query(I r){
    assert(0 <= r && r <= maxn);
    return query(root, r, h - 1);
  }
  Val query(I l, I r){
    assert(0 <= l && l <= r && r <= maxn);
    if(l == r) return Val(0);
    return query(root, r, h - 1) - query(root, l, h - 1);
  }
};
#line 2 ".lib/template.hpp"
#include <iostream>
#include <string>
#line 5 ".lib/template.hpp"
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#line 11 ".lib/template.hpp"
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#line 19 ".lib/template.hpp"
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
template<typename T>
using vec = std::vector<T>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}
#line 3 "a.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n;
  std::cin >> n;

  sparse_binary_indexed_tree<long long> t(1000000001);

  long long ans = 0;
  for(int i = 0; i < n; i++){
    int a, b, c;
    std::cin >> a >> b >> c;
    if(!a){
      t.update(b, c);
    }else{
      ans += t.query(b, c + 1);
    }
  }
  std::cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード