Submit Info #2988

Problem Lang User Status Time Memory
Point Add Range Sum cpp niuez RE 225 ms 12.55 MiB

ケース詳細
Name Status Time Memory
example_00 RE 225 ms 0.66 MiB
max_random_00 RE 111 ms 12.50 MiB
max_random_01 RE 114 ms 12.55 MiB
max_random_02 RE 112 ms 12.46 MiB
max_random_03 RE 112 ms 12.43 MiB
max_random_04 RE 112 ms 12.51 MiB
random_00 RE 109 ms 11.65 MiB
random_01 RE 113 ms 12.17 MiB
random_02 RE 99 ms 2.05 MiB
random_03 RE 113 ms 11.99 MiB
random_04 RE 106 ms 10.80 MiB

#include <bits/stdc++.h> using namespace std; using i64 = long long; template<class T, class Ope, const T& Ide> struct segment_tree { Ope ope; i64 n; vector<T> node; segment_tree(const vector<T>& init) { n = 1; while(n < init.size()) n *= 2; node.resize(2 * n, Ide); for(int i = 0;i < init.size();i++) node[i + n] = init[i]; for(int i = n - 1; i >= 1;i--) node[i] = ope(node[i * 2], node[i * 2 + 1]); } void modify(i64 i, T x) { i += n; node[i] = ope(node[i], x); while(i > 1) { i = i * 2; node[i] = ope(node[i * 2], node[i * 2 + 1]); } } /* [l, r) */ T sum(i64 l, i64 r) const { T lx = Ide; T rx = Ide; l += n; r += n; while(l < r) { if(l & 1) { lx = ope(lx, node[l++]); } if(r & 1) { rx = ope(node[--r], rx); } l >>= 1; r >>= 1; } return ope(lx, rx); } }; #include <cstdio> namespace niu { char cur; struct FIN { static inline bool is_blank(char c) { return c <= ' '; } inline char next() { return cur = getc_unlocked(stdin); } inline char peek() { return cur; } inline void skip() { while(is_blank(next())){} } #define intin(inttype) \ FIN& operator>>(inttype& n) { \ bool sign = 0; \ n = 0; \ skip(); \ while(!is_blank(peek())) { \ if(peek() == '-') sign = 1; \ else n = (n << 1) + (n << 3) + (peek() & 0b1111); \ next(); \ } \ if(sign) n = -n; \ return *this; \ } intin(int) intin(long long) } fin; char tmp[128]; struct FOUT { static inline bool is_blank(char c) { return c <= ' '; } inline void push(char c) { putc_unlocked(c, stdout); } FOUT& operator<<(char c) { push(c); return *this; } FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; } #define intout(inttype) \ FOUT& operator<<(inttype n) { \ if(n) { \ char* p = tmp + 127; bool neg = 0; \ if(n < 0) neg = 1, n = -n; \ while(n) *--p = (n % 10) | 0b00110000, n /= 10; \ if(neg) *--p = '-'; \ return (*this) << p; \ } \ else { \ push('0'); \ return *this; \ } \ } intout(int) intout(long long) } fout; } #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) const i64 plus_ide = 0; int main() { using niu::fout; using niu::fin; int N, Q; fin >> N >> Q; std::vector<i64> init(N); rep(i,0,N) fin >> init[i]; segment_tree<i64, std::plus<i64>, plus_ide> seg(init); i64 q, a, b; while(Q--) { fin >> q >> a >> b; if(q == 0) { seg.modify(a, b); } else { fout << seg.sum(a, b) << '\n'; } } }