結果
問題 | No.789 範囲の合計 |
ユーザー | shkiiii_ |
提出日時 | 2024-03-20 21:21:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 102 ms / 1,000 ms |
コード長 | 3,399 bytes |
コンパイル時間 | 2,072 ms |
コンパイル使用メモリ | 210,980 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 07:06:52 |
合計ジャッジ時間 | 4,481 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 98 ms
6,816 KB |
testcase_03 | AC | 77 ms
6,816 KB |
testcase_04 | AC | 102 ms
6,816 KB |
testcase_05 | AC | 85 ms
6,820 KB |
testcase_06 | AC | 87 ms
6,816 KB |
testcase_07 | AC | 58 ms
6,820 KB |
testcase_08 | AC | 87 ms
6,820 KB |
testcase_09 | AC | 83 ms
6,816 KB |
testcase_10 | AC | 89 ms
6,816 KB |
testcase_11 | AC | 68 ms
6,816 KB |
testcase_12 | AC | 69 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,820 KB |
ソースコード
#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; }