Submit Info #21126

Problem Lang User Status Time Memory
Point Add Range Sum cpp MohammadKhalid WA 420 ms 11.14 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 WA 415 ms 11.10 MiB
max_random_01 WA 415 ms 11.14 MiB
max_random_02 WA 412 ms 11.11 MiB
max_random_03 WA 420 ms 11.09 MiB
max_random_04 WA 407 ms 11.05 MiB
random_00 WA 342 ms 9.80 MiB
random_01 WA 340 ms 10.37 MiB
random_02 WA 256 ms 3.62 MiB
random_03 WA 59 ms 8.05 MiB
random_04 WA 101 ms 7.24 MiB
small_00 WA 1 ms 0.67 MiB
small_01 WA 0 ms 0.62 MiB
small_02 WA 0 ms 0.66 MiB
small_03 WA 4 ms 0.63 MiB
small_04 WA 2 ms 0.70 MiB
small_05 WA 2 ms 0.67 MiB
small_06 WA 2 ms 0.67 MiB
small_07 WA 1 ms 0.65 MiB
small_08 WA 3 ms 0.67 MiB
small_09 WA 1 ms 0.59 MiB

#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef vector<int> vi; #define ff first #define ss second #define pb push_back #define mp make_pair #define sz(v) (int)v.size() #define ll unsigned long long int #define ld long double #define pii pair<int, int> #define pll pair<ll, ll> #define fill(a,v) memset(a,v,sizeof(a)); #define all(v) v.begin(),v.end() #define rep(i, a, b) for(int i = a; i < b; i++) #define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #define trarr(a,n) rep(i,0,n) cerr<<a[i]<<" \n"[i==n-1]; #define trmat(g,n,m) rep(i,0,n)rep(j,0,m) cerr<<g[i][j]<<" \n"[i==m-1]; #define tr(...) cerr<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__) template<typename S, typename T> ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.ff<<", "<<p.ss<<')';return out;} template<typename T> ostream& operator<<(ostream& out,vector<T> const& v){ int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;} template<typename T> void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;} template<typename T, typename... Args> void trace(const char* names, T&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);} const ld PI = acos(-1); const ld EPS = 1e-9; const int inf = 1e9+10; const ll INF = 1e18+10; const int P = 1e9+7; const int N = 2e5+10; /* usage segmentTree<<INPUT_TYPE>, <OUTPUT_TYPE>, <Type_Of_SegmentTreeNode>> finish the implementations of segmentTreeNode time : Merge - O(C) Build - O(N) * O(C) Query - O(LogN * O(C)) Update - O(LogN * O(C)) space : 2*n*sizeOf(segmentTreeNode) */ class node{ public: int value; // segmentTreeNode() {} node(){ value = 0; } void assignLeaf(int v){ value = v; } void merge(node& left, node& right){ //merge nodes left and right this->value = left.value+right.value; } int getValue(){ // return the aggregate value stored in this node. return value; } void updateValue(int v){ this->value+=v; } }; template<typename T, typename V, typename C> class segmentTree{ T *arr; int n; C* tree; public: segmentTree(T arr1[], int n1) : n(n1){ arr = new T[n]; for(int i = 0; i < n; i++) arr[i] = arr1[i]; tree = new C[getSize(n)]; build(); } void build(){ buildUtil(1, 0, n-1); } V query(int l, int r){ C res = queryUtil(l, r, 1, 0, n-1); return res.getValue(); } void update(T value, int idx){ updateUtil(value, idx, 1, 0, n-1); } private: int getSize(int m){ int sz = 1; while(sz < m) sz*=2; return sz*2; } int left(int m){ return 2*m; } int right(int m){ return 2*m+1; } void buildUtil(int index, int lo, int hi){ if(lo == hi) tree[index].assignLeaf(arr[lo]); else { int left = 2*index, right = left+1, mid = lo + (hi-lo)/2; buildUtil(left, lo, mid);buildUtil(right, mid+1, hi); tree[index].merge(tree[left], tree[right]); } } C queryUtil(int l, int r, int index, int lo, int hi){ if( l > r ) return node(); if(l == lo && r == hi)return tree[index]; else { int left = 2*index, right = left+1, mid = lo + (hi-lo)/2; C lRes = queryUtil(l, min(r, mid), left, lo, mid); C rRes = queryUtil(max(l, mid+1), r, right, mid+1, hi); C result; result.merge(lRes, rRes); return result; } } void updateUtil(T value, int updIdx, int index, int lo, int hi){ if(lo == hi)tree[index].updateValue(value); else { int left = 2*index, right = left+1, mid = lo + (hi-lo)/2; if(updIdx > mid) updateUtil(value, updIdx, right, mid+1, hi); else updateUtil(value, updIdx, left, lo, mid); tree[index].merge(tree[left], tree[right]); } } }; void solve(int _t){ int n, q; cin >> n; cin >> q; int a[n]; for(int i = 0; i < n; i++) cin >> a[i]; segmentTree<int, int, node> tree(a, n); while(q--){ int t; cin >> t; if(!t){ int val, id; cin >> id >> val; tree.update(val, id); } else{ int l, r; cin >> l >> r; cout<< tree.query(l, r-1)<<endl; } } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; // cout<<(1ll<<61)<<endl; // cin >> t; rep(test, 1, t+1){ solve(test); } return 0; }