結果

問題 No.789 範囲の合計
コンテスト
ユーザー shkiiii_
提出日時 2024-03-20 21:21:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 116 ms / 1,000 ms
コード長 3,399 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 205,124 KB
最終ジャッジ日時 2025-02-20 08:38:24
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
// #include<atcoder/all>
// #include<boost/multiprecision/cpp_int.hpp>

using namespace std;
// using namespace atcoder;
// using bint = boost::multiprecision::cpp_int;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define sz(c) ((ll)(c).size())
#define LB(A,x) (int)(lower_bound(A.begin(),A.end(),x)-A.begin())
// #define MOD 1000000007
#define MOD 998244353
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<typename T>ostream&operator<<(ostream&os,vector<T>&v){for(int i = 0;i < v.size();i++)os<<v[i]<<(i+1!=v.size()?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}

// https://lorent-kyopro.hatenablog.com/entry/2021/03/12
template<typename T>
struct dynamic_segtree{
  using F = function<T(T,T)>;
  struct node;
  using node_ptr = unique_ptr<node>;
  struct node{
    long long pos;
    T val,subtree_val;
    node_ptr l,r;
    node(long long pos,T val):pos(pos),val(val),subtree_val(val),l(nullptr),r(nullptr){}
  };
  long long n;
  F f;
  T ti;
  node_ptr root;
  dynamic_segtree(long long N,F f,T ti):f(f),ti(ti),root(nullptr){
    n = 1;
    while(n < N)n <<= 1;
  }
  // O(log(n))
  void set(long long pos,T val){
    set(root,pos,val,0,n);
  }
  // [l,r) O(log(n))
  T get(long long l,long long r){
    return get(root,l,r,0,n);
  }
  private:
  void set(node_ptr& t,long long pos,T val,long long left,long long right){
    if(t == nullptr){
      t = make_unique<node>(pos,val);
      return;
    }
    if(t->pos == pos){
      t->val = t->subtree_val = val;
      if(t->l != nullptr)t->subtree_val = f((t->l)->subtree_val,t->subtree_val);
      if(t->r != nullptr)t->subtree_val = f(t->subtree_val,(t->r)->subtree_val);
      return;
    }
    long long mid = (left + right) >> 1;
    if(pos < mid){
      if(t->pos < pos)swap(t->pos,pos),swap(t->val,val);
      set(t->l,pos,val,left,mid);
    }else{
      if(pos < t->pos)swap(pos,t->pos),swap(val,t->val);
      set(t->r,pos,val,mid,right);
    }
    t->subtree_val = t->val;
    if(t->l != nullptr)t->subtree_val = f((t->l)->subtree_val,t->subtree_val);
    if(t->r != nullptr)t->subtree_val = f(t->subtree_val,(t->r)->subtree_val);
  }
  T get(node_ptr &t,long long l,long long r,long long left,long long right){
    if(t == nullptr || right <= l || r <= left)return ti;
    if(l <= left && right <= r)return t->subtree_val;
    long long mid = (left + right) >> 1;
    T res = get(t->l,l,r,left,mid);
    if(l <= t->pos && t->pos < r)res = f(res,t->val);
    return f(res,get(t->r,l,r,mid,right));
  }
};

int main(){
  
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  dynamic_segtree<ll> seg(1ll << 50,[](ll a,ll b){return a + b;},0);
  ll res = 0;
  while(n--){
    ll t,l,r;
    cin >> t >> l >> r;
    if(t == 0){
      ll k = seg.get(l,l+1);
      seg.set(l,k + r);
    }else{
      res += seg.get(l,r+1);
    }
  }
  cout << res << "\n";
  

  return 0;
}
0