Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3644

Problem Lang User Status Time Memory
Point Add Range Sum cpp (anonymous) AC 792 ms 16.25 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
max_random_00 AC 786 ms 16.25 MiB
max_random_01 AC 783 ms 16.17 MiB
max_random_02 AC 792 ms 16.17 MiB
max_random_03 AC 773 ms 16.25 MiB
max_random_04 AC 781 ms 16.25 MiB
random_00 AC 641 ms 14.80 MiB
random_01 AC 675 ms 14.84 MiB
random_02 AC 464 ms 7.29 MiB
random_03 AC 163 ms 9.00 MiB
random_04 AC 217 ms 10.14 MiB
small_00 AC 8 ms 0.63 MiB
small_01 AC 6 ms 0.63 MiB
small_02 AC 7 ms 0.62 MiB
small_03 AC 8 ms 0.62 MiB
small_04 AC 7 ms 0.67 MiB
small_05 AC 7 ms 0.59 MiB
small_06 AC 8 ms 0.64 MiB
small_07 AC 8 ms 0.63 MiB
small_08 AC 7 ms 0.67 MiB
small_09 AC 7 ms 0.64 MiB

#include<iostream> #include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<string> #include<map> #include<string.h> #include<complex> #include<math.h> #include<queue> #include <functional> #include<time.h> using namespace std; typedef long long int llint; typedef pair<int, int> pint; typedef pair<llint, llint> pllint; typedef vector<int> vint; typedef vector<llint> vllint; typedef vector<pint> vpint; typedef vector<string> vstring; typedef vector<pair<llint, llint>> vpllint; typedef vector<vector<int>> vvint; typedef vector<vector<llint>> vvllint; typedef vector<vector<pint>> vvpint; typedef vector<bool> vbool; #define rep(i,n) for(int i=0;i<n;i++) #define drep(i,n) for(int i=n-1;0<=i;i--) #define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl; #define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl; #define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl; #define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl; #define Pi 3.1415926535897932384626 #define mod llint(1e9+7) #define Inf 2147483647 class UnionFind { public: //親の番号を格納する。親だった場合は-(その集合のサイズ) vector<int> Parent; //作るときはParentの値を全て-1にする //こうすると全てバラバラになる UnionFind(int N) { Parent = vector<int>(N, -1); } //Aがどのグループに属しているか調べる int root(int A) { if (Parent[A] < 0) return A; return Parent[A] = root(Parent[A]); } //自分のいるグループの頂点数を調べる int size(int A) { return -Parent[root(A)];//親をとってきたい } //AとBをくっ付ける bool connect(int A, int B) { //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける A = root(A); B = root(B); if (A == B) { //すでにくっついてるからくっ付けない return false; } //大きい方(A)に小さいほう(B)をくっ付けたい //大小が逆だったらひっくり返しちゃう。 if (size(A) < size(B)) swap(A, B); //Aのサイズを更新する Parent[A] += Parent[B]; //Bの親をAに変更する Parent[B] = A; return true; } }; //セグ木・0-indexed・非再帰・(大きさ・単位元)で初期化 template<typename T> struct SegTree { //比較関数の型 using F = function<T(T, T)>; //二分木を配列で表したもの vector<T>seg; //木の半分の大きさ int siz; //単位元 const T unit; //比較する関数 const F f; //大きさn、unit(単位元)でsegtreeを初期化する SegTree(int n, const T unit, const F f) : unit(unit), f(f) { siz = 1; while (siz < n)siz <<= 1; seg.assign(siz * 2 - 1, unit); siz--; } //k番目にtを入力 void set(int k, const T& t) { seg[k + siz] = t; } //fによって木を構築する void build() { for (int i = siz - 1; 0 <= i; i--) { seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]); } } T operator[](const int i) { return seg[i + siz]; } //k番目をxに更新する void update(int k, T x) { k += siz; seg[k] = x; while (0 < k) { k = (k - 1) >> 1; seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[a,b)について、fした結果を返す //半開区域のためa以上b未満の位置を指す T query(int a, int b) { T l = unit, r = unit; for (a += siz, b += siz; a < b; a >>= 1, b >>= 1) { if (!(a & 1))l = f(seg[a++], l); if (!(b & 1))r = f(seg[--b], r); } return f(l, r); } }; //aとbの最大公約数を求めるよ long long GCD(long long a, long long b) { if (b == 0) return a; else return GCD(b, a % b); } // 返り値: a と b の最大公約数 // ax + by = gcd(a, b) を満たす (x, y) が格納される long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } bool check(llint a, llint b) { return a > b; } // mod. m での a の逆元 a^{-1} を計算する long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } //aCbを1000000007で割った余りを求める llint convination(llint a, llint b) { llint ans = 1; for (llint i = 0; i < b; i++) { ans *= a - i; ans %= 1000000007; } for (llint i = 1; i <= b; i++) { ans *= modinv(i, 1000000007); ans %= 1000000007; } return ans; } //aのb乗をmodで割った余りを求める llint power(llint a, llint b) { if (b == 1)return a; if (b == 0)return 1; llint tmp = power(a, (llint)b / 2); tmp *= tmp; tmp %= mod; if (b % 2 == 1) { tmp *= a; tmp %= mod; } return tmp; } int main() { int n, q; cin >> n >> q; SegTree<llint> ST(n, 0, [](llint a, llint b) {return a + b; }); rep(i, n) { llint x; cin >> x; ST.set(i, x); } ST.build(); vllint ans(q); rep(i, q) { int x; cin >> x; if (x == 0) { int a, b; cin >> a >> b; ST.update(a, ST.operator[](a) + b); ans[i] = -1; } else { int l, r; cin >> l >> r; ans[i] = ST.query(l, r); } } rep(i, q)if (ans[i] >= 0) cout << ans[i] << endl; return 0; }