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

• 問題: No.789 範囲の合計
• ユーザー: tonegawa
• 提出日時: 2021-03-31 21:25:29
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 92 ms / 1,000 ms
• コード長: 12,254 bytes
• コンパイル時間: 1,700 ms
• コンパイル使用メモリ: 139,100 KB
• 実行使用メモリ: 7,552 KB
• 最終ジャッジ日時: 2024-05-09 05:18:22
• 合計ジャッジ時間: 3,757 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	90 ms; 6,784 KB
testcase_03	AC	38 ms; 5,376 KB
testcase_04	AC	92 ms; 7,296 KB
testcase_05	AC	63 ms; 6,656 KB
testcase_06	AC	63 ms; 6,784 KB
testcase_07	AC	29 ms; 5,376 KB
testcase_08	AC	60 ms; 7,552 KB
testcase_09	AC	54 ms; 7,168 KB
testcase_10	AC	85 ms; 5,504 KB
testcase_11	AC	78 ms; 7,040 KB
testcase_12	AC	77 ms; 7,168 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define all(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)
#define c2(n) ((ll(n)*(n-1))/2)
#define c3(n) (((ll(n)*(n-1))*(n-2))/6)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

constexpr uint32_t MASK32 = 0xffffffff;
constexpr uint32_t SIGN32 = 0x80000000;
uint64_t encode_signed(int a, int b){return ((uint64_t(a)+SIGN32)<<32)+(uint64_t(b)+SIGN32);}
pi decode_signed(uint64_t x){return {int((x>>32)-SIGN32),int((x&MASK32)-SIGN32)};}
ll encode(int a, int b){return (ll(a)<<32)+b;}
pi decode(ll x){return {x>>32,x&MASK32};}

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;
}
template<typename T>
bool mul_overflow(T a, T b){
  static T INF = numeric_limits<T>::max();
  return (INF / a) < b;
}
template<typename T>
bool add_overflow(T a, T b){
  static T INF = numeric_limits<T>::max();
  return (INF - a) < b;
}
template<typename T>
bool chmax(T &a, const T b){
  if(a >= b) return false;
  a = b;
  return true;
}
template<typename T>
bool chmin(T &a, const T b){
  if(a <= b) return false;
  a = b;
  return true;
}
template<typename T>
T max(vector<T> &v, int l=0, int r = -1){
  return *std::max_element(v.begin()+l, v.begin()+(r==-1?v.size():r));
}
template<typename T>
T min(vector<T> &v, int l=0, int r = -1){
  return *std::min_element(v.begin()+l, v.begin()+(r==-1?v.size():r));
}
template<typename T>
int argmax(vector<T> &v, int l=0, int r=-1){
  T res = max(v, l, r);
  if(r==-1) r = v.size();
  for(int i=l;i<r;i++) if(v[i]==res) return i;
  return -1;
}
template<typename T>
int argmin(vector<T> &v, int l=0, int r=-1){
  T res = min(v, l, r);
  if(r==-1) r = v.size();
  for(int i=l;i<r;i++) if(v[i]==res) return i;
  return -1;
}
ll gcd(ll _a, ll _b) {
  uint64_t a = abs(_a), b = abs(_b);
  if(a == 0) return b;
  if(b == 0) return a;
  int shift = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do{
    b >>= __builtin_ctzll(b);
    if(a > b) std::swap(a, b);
    b -= a;
  }while(b);
  return (a << shift);
}
ll lcm(ll a, ll b){
  return (a / gcd(a, b)) * b;
}
ll llpow(ll a, ll b){
  ll ret = 1, mul = a;
  while(b){
    if(b&1) ret *= mul;
    mul *= mul;
    b >>= 1;
  }
  return ret;
}
template<int MOD>
ll mpow(ll a, ll b){
  int ret = (MOD==1?0:1), mul = a % MOD;
  while(b){
    if(b&1) ret = (ll(ret) * mul) % MOD;
    mul = (ll(mul) * mul) % MOD;
    b >>= 1;
  }
  return ret;
}
ll mpow(ll a, ll b, ll MOD){
  int ret = (MOD==1?0:1), mul = a % MOD;
  while(b){
    if(b&1) ret = (ll(ret) * mul) % MOD;
    mul = (ll(mul) * mul) % MOD;
    b >>= 1;
  }
  return ret;
}

template<typename K, typename T>
struct rbtree_range_query{
private:
  using F = function<T(T, T)>;
  F f;
  struct node{
    K key;
    T val, sum;
    int red, sz;
    node *par, *ch[2];
    node(): red(0), sz(0){}
    node(K key, T val):key(key), val(val), red(1), sz(1){
      par = ch[0] = ch[1] = nullptr;
    }
  };
  void print(node *v, int dep, int lr){
    if(v == nil) return;
    print(v->ch[1], dep+1, 1);
    for(int i = 0; i < dep; i++) cerr << "  ";
    if(!lr) cerr << "--";
    else if(lr == 1) cerr << "「";
    else cerr << "Ｌ";
    if(v->red) cerr << "\x1b[31m";
    cerr << v->key << endl;
    assert(v->sz == 1 + v->ch[0]->sz + v->ch[1]->sz);
    cerr << "\x1b[0m";
    print(v->ch[0], dep+1, 2);
  }
  inline void eval(node *v){
    if(v==nil) return;
    v->sum = v->val;
    if(v->ch[0]!=nil) v->sum = f(v->ch[0]->sum, v->sum);
    if(v->ch[1]!=nil) v->sum = f(v->sum, v->ch[1]->sum);
    v->sz = 1 + v->ch[0]->sz + v->ch[1]->sz;
  }
  void rec_eval(node *v){
    if(v==nil) v = v->par;
    while(v!=nil){
      eval(v);
      v = v->par;
    }
  }
  void rotate(node *x, int d){
    int e = d^1;
    node *y = x->ch[e];
    x->ch[e] = y->ch[d];
    eval(x);
    if(y->ch[d]!=nil) y->ch[d]->par = x;
    y->par = x->par;
    if(x->par==nil) root = y;
    else if(x==x->par->ch[d]) x->par->ch[d] = y, eval(x->par);
    else x->par->ch[e] = y, eval(x->par);
    y->ch[d] = x;
    eval(y);
    x->par = y;
  }
  node *minimum(node* x){
    while(x->ch[0]!=nil) x = x->ch[0];
    return x;
  }
  void transplant(node *u, node *v){
    if(u->par==nil) root = v;
    else if(u==u->par->ch[0]) u->par->ch[0] = v;
    else u->par->ch[1] = v;
    v->par = u->par;
  }

  void insert_update(node *z){
    node *y;
    while(z->par->red){
      int d = (z->par==z->par->par->ch[0]?0:1), e = d^1;
      y = z->par->par->ch[e];
      if(y->red){
        z->par->red = 0;
        y->red = 0;
        z->par->par->red = 1;
        z = z->par->par;
      }else if(z==z->par->ch[e]){
        z = z->par;
        rotate(z,d);
      }else{
        z->par->red = 0;
        z->par->par->red = 1;
        rotate(z->par->par,e);
      }
    }
    root->red = 0;
  }
  node *build(int l, int r, int d, node *parent, const vector<pair<K, T>> &v){
    int mid = (r+l)/2;
    node *now = new node(v[mid].first, v[mid].second);
    now->red = d;
    now->par = parent;
    if(mid>l) now->ch[0] = build(l, mid, d^1, now, v);
    else now->ch[0] = nil;
    if(r>mid+1) now->ch[1] = build(mid+1, r, d^1, now, v);
    else now->ch[1] = nil;
    eval(now);
    return now;
  }
  T inner_query(node *v, K l, K r){
    if(l<0) l = 0;
    if(l>=r||v==nil) return z1;
    if(v->sz==r-l) return v->sum;
    int lsz = v->ch[0]->sz;
    if(lsz<=l){
      return (lsz==l?f(v->val, inner_query(v->ch[1], 0, r-lsz-1)):inner_query(v->ch[1], l-lsz-1, r-lsz-1));
    }else if(r-1<=lsz){
      return (r-1==lsz?f(inner_query(v->ch[0], l, r-1), v->val):inner_query(v->ch[0], l, r));
    }else{
      return (l==0?f((v->ch[0]!=nil?f(v->ch[0]->sum, v->val):v->val), inner_query(v->ch[1], 0, r-lsz-1)):f(inner_query(v->ch[0], l, lsz), f(v->val, inner_query(v->ch[1], 0, r-lsz-1))));
    }
  }
public:
  node *root, *nil;
  T z1;
  rbtree_range_query(F f=[](T a, T b){return a+b;}, T z1=0):f(f), z1(z1){
    nil = new node();
    root = nil->par = nil->ch[0] = nil->ch[1] = nil;
  }
  rbtree_range_query(vector<pair<K, T>> v, F f=[](T a, T b){return a+b;}, T z1=0):f(f), z1(z1){
    nil = new node();
    sort(v.begin(), v.end());
    root = build(0, v.size(), 0, nil, v);
  }
  void print(){
    print(root, 0, 0);
  }
  int size(){
    return root->sz;
  }
  node *find(K key){
    node *x = root;
    while(x != nil){
      if(key != x->key) x = x->ch[key > x->key];
      else return x;
    }
    return x;
  }
  node *insert(K key, T val){
    node *x = root, *y = nil;
    while(x!=nil){
      y = x;
      if(key != x->key) x = x->ch[key > x->key];
      else{
        x->val = f(x->val, val);
        rec_eval(x);
        return x;
      }
    }
    node *z = new node(key, val);
    z->par = y;
    if(y==nil) root = z;
    else y->ch[z->key >= y->key] = z, eval(y);
    z->ch[0] = z->ch[1] = nil;
    insert_update(z);
    nil->par = nil->ch[0] = nil->ch[1] = nil;
    rec_eval(z);
    return z;
  }

  void erase(node *z){
   if(z==nil) return;
   node *y = z, *x;
   int prevy = y->red;
   if(z->ch[0]==nil){
     x = z->ch[1];
     transplant(z, z->ch[1]);
     rec_eval(z);
   }else if(z->ch[1]==nil){
     x = z->ch[0];
     transplant(z, z->ch[0]);
     rec_eval(z);
   }else{
     y = minimum(z->ch[1]);
     prevy = y->red;
     x = y->ch[1];
     if(y->par==z){
       x->par = y;
       transplant(z, y);
       y->ch[0] = z->ch[0];
       y->ch[0]->par = y;
       y->red = z->red;
       rec_eval(y);
     }else{
       transplant(y, y->ch[1]);
       node *tmp = y->par;
       y->ch[1] = z->ch[1];
       y->ch[1]->par = y;
       transplant(z, y);
       y->ch[0] = z->ch[0];
       y->ch[0]->par = y;
       y->red = z->red;
       rec_eval(tmp);
     }
   }
   if(!prevy) x->red = 0;
   delete z;
   nil->par = nil->ch[0] = nil->ch[1] = nil;
 }
  void erase(K key){
    erase(find(key));
  }
  node *lower_bound(K key){
    node *x = root, *y;
    while(x != nil){
      if(x->key>=key) y = x;
      if(key != x->key) x = x->ch[key > x->key];
      else return x;
    }
    return y;
  }
  node *upper_bound(K key){
    node *x = root, *y;
    while(x != nil){
      if(x->key>key) y = x;
      x = x->ch[key >= x->key];
    }
    return y;
  }
  node *reverse_lower_bound(K key){
    node *x = root, *y;
    while(x != nil){
      if(x->key<=key) y = x;
      if(key != x->key) x = x->ch[key > x->key];
      else return x;
    }
    return y;
  }
  node *reverse_upper_bound(K key){
    node *x = root, *y;
    while(x != nil){
      if(x->key<key) y = x;
      x = x->ch[key > x->key];
    }
    return y;
  }
  int under_count(K key){
    node *x = root;
    int ret = 0;
    while(x != nil){
      if(x->key<=key) ret += (x->key!=key) + x->ch[0]->sz;
      if(key != x->key) x = x->ch[key > x->key];
      else return ret;
    }
    return ret;
  }
  node *kth_element(int k){
    if(root->sz<=k) return nil;
    node *x = root;
    while(x!=nil){
      int lsz = x->ch[0]->sz;
      if(k==lsz) return x;
      if(lsz<k) k -= lsz + 1, x = x->ch[1];
      else x = x->ch[0];
    }
    return nil;
  }
  T query_size(int l, int r){
    l = max(l, 0);
    r = min(r, size());
    if(l>=r) return z1;
    return inner_query(root, l, r);
  }
  T query_val(K l, K r){
    return query_size(under_count(l), under_count(r));
  }
};

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int q;std::cin >> q;
  rbtree_range_query<int, int> rb;
  ll ans = 0;
  for(int i=0;i<q;i++){
    int a, b, c;std::cin >> a >> b >> c;
    if(a==0) rb.insert(b, c);
    else ans += rb.query_val(b, c+1);
  }
  std::cout << ans << '\n';
}