結果

問題 No.789 範囲の合計
ユーザー tonegawatonegawa
提出日時 2023-05-16 06:08:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 68 ms / 1,000 ms
コード長 6,088 bytes
コンパイル時間 1,306 ms
コンパイル使用メモリ 137,784 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2024-05-08 07:04:54
合計ジャッジ時間 2,834 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 64 ms
7,808 KB
testcase_03 AC 44 ms
5,376 KB
testcase_04 AC 68 ms
8,448 KB
testcase_05 AC 50 ms
7,424 KB
testcase_06 AC 52 ms
7,680 KB
testcase_07 AC 37 ms
5,376 KB
testcase_08 AC 53 ms
8,832 KB
testcase_09 AC 50 ms
8,320 KB
testcase_10 AC 66 ms
6,272 KB
testcase_11 AC 46 ms
8,320 KB
testcase_12 AC 43 ms
8,192 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "sparse_bit.hpp"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>

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;
    node(I idx, Val val): idx(idx), val(val), sum(val){}
  };
  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);
  }
  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 = 0; i < maxk; i++) if(v->ch[i]) res += v->ch[i]->sum;
    if(v->ch.size() > k) 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 3 ".lib/template.hpp"
#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"

#line 5 "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';
}
0