test/aoj/DSL_2_G.BIT_rangeadd.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:17:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G

Depends on

• Binary-Indexed-Tree(区間加算) (src/DataStructure/BinaryIndexedTree_RangeAdd.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/DataStructure/BinaryIndexedTree_RangeAdd.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 BinaryIndexedTree_RangeAdd<long long> bit(N);
 while (Q--) {
  int op, s, t;
  cin >> op >> s >> t;
  --s;
  if (op) cout << bit.sum(s, t) << '\n';
  else {
   long long x;
   cin >> x;
   bit.add_range(s, t, x);
  }
 }
}

#line 1 "test/aoj/DSL_2_G.BIT_rangeadd.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/DataStructure/BinaryIndexedTree_RangeAdd.hpp"
#include <vector>
template <typename T> class BinaryIndexedTree_RangeAdd {
 std::vector<T> dat1, dat2;
public:
 BinaryIndexedTree_RangeAdd(int n): dat1(n + 1, T()), dat2(n + 1, T()) {}
 void add_range(int l, int r, T w) {  // add w [l,r)
  int n= dat1.size();
  for (int k= l + 1; k < n; k+= k & -k) dat1[k]-= w * l;
  for (int k= r + 1; k < n; k+= k & -k) dat1[k]+= w * r;
  for (int k= l + 1; k < n; k+= k & -k) dat2[k]+= w;
  for (int k= r + 1; k < n; k+= k & -k) dat2[k]-= w;
 }
 T sum(int x) const {  // sum [0,x)
  T s= 0;
  for (int k= x; k; k&= k - 1) s+= dat2[k];
  s*= x;
  for (int k= x; k; k&= k - 1) s+= dat1[k];
  return s;
 }
 T sum(int l, int r) const { return sum(r) - sum(l); }  // sum [l,r)
 T operator[](size_t k) const { return sum(k + 1) - sum(k); }
};
#line 6 "test/aoj/DSL_2_G.BIT_rangeadd.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 BinaryIndexedTree_RangeAdd<long long> bit(N);
 while (Q--) {
  int op, s, t;
  cin >> op >> s >> t;
  --s;
  if (op) cout << bit.sum(s, t) << '\n';
  else {
   long long x;
   cin >> x;
   bit.add_range(s, t, x);
  }
 }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	00_sample_01.in	AC	5 ms	4 MB
g++-13	01_rand_00.in	AC	4 ms	4 MB
g++-13	01_rand_01.in	AC	4 ms	4 MB
g++-13	01_rand_02.in	AC	4 ms	4 MB
g++-13	01_rand_03.in	AC	5 ms	4 MB
g++-13	01_rand_04.in	AC	5 ms	4 MB
g++-13	01_rand_05.in	AC	6 ms	4 MB
g++-13	02_corner_00.in	AC	4 ms	4 MB
g++-13	02_corner_01.in	AC	4 ms	4 MB
g++-13	03_large_00.in	AC	7 ms	4 MB
g++-13	03_large_01.in	AC	7 ms	4 MB
g++-13	03_large_02.in	AC	7 ms	4 MB
g++-13	03_large_03.in	AC	7 ms	4 MB
g++-13	04_maximum_00.in	AC	29 ms	5 MB
g++-13	04_maximum_01.in	AC	30 ms	5 MB
g++-13	04_maximum_02.in	AC	31 ms	5 MB
g++-13	04_maximum_03.in	AC	29 ms	5 MB
g++-13	05_critical_00.in	AC	29 ms	5 MB
g++-13	05_critical_01.in	AC	26 ms	5 MB
g++-13	05_critical_02.in	AC	31 ms	5 MB
g++-13	05_critical_03.in	AC	28 ms	5 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	5 ms	4 MB
clang++-18	01_rand_00.in	AC	4 ms	4 MB
clang++-18	01_rand_01.in	AC	4 ms	4 MB
clang++-18	01_rand_02.in	AC	4 ms	4 MB
clang++-18	01_rand_03.in	AC	5 ms	4 MB
clang++-18	01_rand_04.in	AC	5 ms	4 MB
clang++-18	01_rand_05.in	AC	6 ms	4 MB
clang++-18	02_corner_00.in	AC	5 ms	4 MB
clang++-18	02_corner_01.in	AC	4 ms	4 MB
clang++-18	03_large_00.in	AC	7 ms	4 MB
clang++-18	03_large_01.in	AC	7 ms	4 MB
clang++-18	03_large_02.in	AC	7 ms	4 MB
clang++-18	03_large_03.in	AC	7 ms	4 MB
clang++-18	04_maximum_00.in	AC	30 ms	5 MB
clang++-18	04_maximum_01.in	AC	30 ms	5 MB
clang++-18	04_maximum_02.in	AC	31 ms	5 MB
clang++-18	04_maximum_03.in	AC	27 ms	5 MB
clang++-18	05_critical_00.in	AC	27 ms	5 MB
clang++-18	05_critical_01.in	AC	23 ms	5 MB
clang++-18	05_critical_02.in	AC	30 ms	5 MB
clang++-18	05_critical_03.in	AC	27 ms	5 MB

Back to top page