test/verify/yosupo-static-range-sum.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 11:04:56+00:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• Cumulative Sum (一次元累積和) (dp/cumulative-sum.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_sum
// clang-format on

#include <iostream>

#include "../../dp/cumulative-sum.hpp"

using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  CumulativeSum<long long> cs(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cs.add(i, x);
  }
  cs.build();
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    cout << cs.fold(l, r) << "\n";
  }
}

#line 1 "test/verify/yosupo-static-range-sum.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_sum
// clang-format on

#include <iostream>

#line 2 "dp/cumulative-sum.hpp"

#include <algorithm>
#include <cstddef>
#include <vector>

template <class T>
struct CumulativeSum {
  std::vector<T> data;

  CumulativeSum() = default;

  explicit CumulativeSum(std::size_t sz) : data(sz + 1, 0) {}

  void add(int k, const T& x) { data[k + 1] += x; }

  void build() {
    for (int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  T fold(int r) const {
    if (r < 0) return 0;
    return data[std::min(r, (int)data.size() - 1)];
  }

  T fold(int l, int r) const { return fold(r) - fold(l); }
};
#line 8 "test/verify/yosupo-static-range-sum.test.cpp"

using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  CumulativeSum<long long> cs(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cs.add(i, x);
  }
  cs.build();
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    cout << cs.fold(l, r) << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	2 ms	4 MB
g++	max_random_00	AC	869 ms	7 MB
g++	max_random_01	AC	1012 ms	7 MB
g++	max_random_02	AC	869 ms	7 MB
g++	max_random_03	AC	1393 ms	7 MB
g++	max_random_04	AC	1178 ms	7 MB
g++	random_00	AC	653 ms	6 MB
g++	random_01	AC	1132 ms	7 MB
g++	random_02	AC	785 ms	4 MB
g++	random_03	AC	157 ms	7 MB
g++	random_04	AC	211 ms	6 MB
clang++	example_00	AC	2 ms	4 MB
clang++	max_random_00	AC	1046 ms	7 MB
clang++	max_random_01	AC	858 ms	7 MB
clang++	max_random_02	AC	1155 ms	7 MB
clang++	max_random_03	AC	1045 ms	7 MB
clang++	max_random_04	AC	1011 ms	7 MB
clang++	random_00	AC	671 ms	6 MB
clang++	random_01	AC	743 ms	7 MB
clang++	random_02	AC	825 ms	4 MB
clang++	random_03	AC	184 ms	7 MB
clang++	random_04	AC	226 ms	6 MB

Back to top page