You are given a sequence of n integers a_1, a_2, …, a_n and q queries. Each query consists of two numbers l and r and asks for the sum of a_l through a_r (both ends included). Print the answer to each query on its own line, in the order the queries are given.
The first line has n and q, the second line has a_1 … a_n, and each of the next q lines has l and r separated by a space.
Input
1 ≤ n ≤ 10,000, 1 ≤ q ≤ 20,000, -10^9 ≤ a_i ≤ 10^9, 1 ≤ l ≤ r ≤ n
Output
q lines, each with the sum for that query
Example 1 · stdin
5 3
3 -1 4 1 -5
1 3
2 5
4 4
stdout
6
-1
1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Adding l through r again for every query can take 10^4 × 2×10^4 = 2×10^8 additions, which Python cannot finish in time (C and C++ still cope, but not once n and q grow). Craykon stops with “taking too long” after about 50 million steps, so there this approach always times out, whatever the machine. Build prefix sums P[i] = a_1 + … + a_i (P[0] = 0) once, and every answer is just P[r] - P[l-1]. Common mistakes: writing P[r] - P[l], which drops a_l, and storing sums of up to 10^13 in an int (about 2.1 billion) in C, C++, Java or C#; use long/long long. Python integers are unbounded, and JavaScript, TypeScript and Craykon are exact up to 2^53, so they are fine. The input is large, so read it fast: Python sys.stdin, Java BufferedReader, C++ sync_with_stdio(false). A Craykon list holds at most 10,000 items, so instead of an (n + 1)-slot P, turn a into prefix sums in place with a[i] = a[i] + a[i - 1], and read each query line with Console.ReadNumbers().
const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = t;const prefix = new Array(n + 1).fill(0); // prefix[i] = 앞에서 i개의 합for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + t[2 + i];const out = [];for (let k = 0, pos = 2 + n; k < q; k++, pos += 2) { const l = t[pos], r = t[pos + 1]; out.push(prefix[r] - prefix[l - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 11 lines
import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = t;const prefix: number[] = new Array(n + 1).fill(0); // prefix[i] = 앞에서 i개의 합for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + t[2 + i];const out: number[] = [];for (let k = 0, pos = 2 + n; k < q; k++, pos += 2) { const l = t[pos], r = t[pos + 1]; out.push(prefix[r] - prefix[l - 1]);}console.log(out.join("\n"));
JavaMain.java · 22 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken()); long[] prefix = new long[n + 1]; // prefix[i] = 앞에서 i개의 합 st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); int l = Integer.parseInt(st.nextToken()), r = Integer.parseInt(st.nextToken()); out.append(prefix[r] - prefix[l - 1]).append('\n'); } System.out.print(out); }}
C#Main.cs · 21 lines
using System;using System.IO;using System.Text;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), q = int.Parse(t[1]); long[] prefix = new long[n + 1]; // prefix[i] = 앞에서 i개의 합 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + long.Parse(t[2 + i]); var sb = new StringBuilder(); for (int k = 0, pos = 2 + n; k < q; k++, pos += 2) { int l = int.Parse(t[pos]), r = int.Parse(t[pos + 1]); sb.Append(prefix[r] - prefix[l - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 20 lines
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<long long> prefix(n + 1, 0); // prefix[i] = 앞에서 i개의 합 for (int i = 0; i < n; i++) { long long x; std::cin >> x; prefix[i + 1] = prefix[i] + x; } for (int k = 0; k < q; k++) { int l, r; std::cin >> l >> r; std::cout << prefix[r] - prefix[l - 1] << '\n'; }}
Cmain.c · 21 lines
#include <stdio.h>#include <stdlib.h>int main(void) { int n, q; scanf("%d %d", &n, &q); long long *prefix = malloc((n + 1) * sizeof *prefix); // prefix[i] = 앞에서 i개의 합 prefix[0] = 0; for (int i = 0; i < n; i++) { long long x; scanf("%lld", &x); prefix[i + 1] = prefix[i] + x; } for (int k = 0; k < q; k++) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", prefix[r] - prefix[l - 1]); } free(prefix); return 0;}
Craykonmain.cray · 23 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];// a를 그 자리에서 누적 합으로 바꾼다: a[i] = 앞에서 i+1개의 합a = Console.ReadNumbers();for (i = 1; i < n; i++){ a[i] = a[i] + a[i - 1];}for (k = 0; k < q; k++){ lr = Console.ReadNumbers(); l = lr[0]; r = lr[1]; if (l == 1) { Console.WriteLine(a[r - 1]); } else { Console.WriteLine(a[r - 1] - a[l - 2]); }}