n guests are sitting around a round table.
The seats are numbered 1, 2, …, n clockwise, and the seat clockwise next to seat n is seat 1.
Serving the dish of the guest in seat i takes t_i seconds.
A waiter starts at seat s and goes around in one direction, serving k guests sitting in a row one after another.
The time a guest waits is the sum of the times taken to serve the guests served before them. The time for their own dish is not included.
You are given q questions.
For each question "s k", print on one line the total time the k guests wait when going clockwise and the total time they wait when going counterclockwise, separated by one space.
For the first question "1 3" of example 1, going clockwise the guests in seats 1, 2 and 3 wait 0, 3 and 4 seconds in turn, 7 in total. Going counterclockwise the guests in seats 1, 5 and 4 wait 0, 3 and 8 seconds in turn, 11 in total.
Input
The first line gives n and q separated by one space. The second line gives t_1, …, t_n separated by single spaces. Each of the next q lines gives s and k separated by one space. 1 ≤ n ≤ 9,000, 1 ≤ q ≤ 7,000, 1 ≤ t_i ≤ 10^8, 1 ≤ s ≤ n, 1 ≤ k ≤ n (all integers)
Output
For each question one line with the total when going clockwise and the total when going counterclockwise
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
The serving time of the guest served j-th (counting from 0) is waited by all k-1-j guests served after them. So the answer is the sum of t × (k-1-j), and the multiplier drops by 1 each time you move one seat. A sum like this comes from two running totals. P[i] is the sum of the first i values of t, and Q[i] is the sum of seat index × t (seat indexes start at 0). Going over seats a to b-1 toward larger indexes, with multiplier c at seat a, the sum is c × (P[b] - P[a]) - ((Q[b] - Q[a]) - a × (P[b] - P[a])). Going toward smaller indexes uses Q the other way round. Because the table is round, going past seat n splits the walk into two pieces. The multiplier of the first guest in the second piece is reduced by the number of people in the first piece. The two small calculations are grouped as nested functions in Python, lambdas in C++, static methods in Java and C#, and plain functions in C, JavaScript, TypeScript and Craykon. The running-total lists are created filled with zeros, as in Python [0] * (n + 1), JavaScript new Array(n + 1).fill(0) and Craykon NewList(n + 1, 0). Trap one: going over the k guests one by one for every question makes about 120 million additions on the largest input. A Python solution written this way did not finish in time, and Craykon also stopped, saying it was taking too long. To be honest, a C solution written the same way finished within 0.3 seconds on this computer. The running totals are really needed only in the slow languages. Trap two: the multiplier must not start again from k-1 in the second piece. The second question "4 4" of example 1 has a clockwise total of 16 but you get 24, and the counterclockwise total of the first question is 11 but you get 17. Trap three: including the time for a guest's own dish (starting the multiplier from k) turns the first question of example 1 into 15 20 instead of 7 11, and even the third question with a single guest into 1 1 instead of 0 0. Trap four: the k guests visited counterclockwise are the same people as k guests visited clockwise from some seat, but the order is reversed, so the total differs. Computing the counterclockwise walk of the first question of example 1 (seats 1, 5, 4) as the clockwise walk starting at seat 4 (seats 4, 5, 1) gives 7 instead of 11. Trap five: the answer grows up to about 4 × 10^15. Java, C#, C and C++ must keep the running totals and the answers in long/long long. Keeping everything in Java int prints -1494967296 instead of 2800000000 for the first question of example 2. Python integers have no size limit. Numbers in JavaScript, TypeScript and Craykon are exact only up to 2^53 (about 9.007 × 10^15), but in this problem even the products that appear on the way never exceed about 8.1 × 10^15, so they are right as they are.
Pythonmain.py · 42 lines
import sysdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) t = [int(x) for x in data[2:2 + n]] # P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 P = [0] * (n + 1) Q = [0] * (n + 1) for i in range(n): P[i + 1] = P[i] + t[i] Q[i + 1] = Q[i] + i * t[i] def forward(a, b, c): """자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다.""" dp = P[b] - P[a] return c * dp - ((Q[b] - Q[a]) - a * dp) def backward(a, b, c): """자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다.""" dp = P[b] - P[a] return c * dp - ((b - 1) * dp - (Q[b] - Q[a])) out = [] pos = 2 + n for _ in range(q): s, k = int(data[pos]) - 1, int(data[pos + 1]) pos += 2 if s + k <= n: cw = forward(s, s + k, k - 1) else: cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)) if k <= s + 1: ccw = backward(s - k + 1, s + 1, k - 1) else: ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)) out.append("%d %d" % (cw, ccw)) print("\n".join(out))main()
JavaScriptmain.js · 36 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합const P = new Array(n + 1).fill(0);const Q = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) { P[i + 1] = P[i] + data[2 + i]; Q[i + 1] = Q[i] + i * data[2 + i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다function forward(a, b, c) { const dp = P[b] - P[a]; return c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다function backward(a, b, c) { const dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}const out = [];for (let i = 0; i < q; i++) { const s = data[2 + n + 2 * i] - 1; const k = data[3 + n + 2 * i]; let cw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); let ccw; if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.push(cw + " " + ccw);}console.log(out.join("\n"));
TypeScriptmain.ts · 37 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합const P: number[] = new Array<number>(n + 1).fill(0);const Q: number[] = new Array<number>(n + 1).fill(0);for (let i = 0; i < n; i++) { P[i + 1] = P[i] + data[2 + i]; Q[i + 1] = Q[i] + i * data[2 + i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다function forward(a: number, b: number, c: number): number { const dp = P[b] - P[a]; return c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다function backward(a: number, b: number, c: number): number { const dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}const out: string[] = [];for (let i = 0; i < q; i++) { const s = data[2 + n + 2 * i] - 1; const k = data[3 + n + 2 * i]; let cw: number; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); let ccw: number; if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.push(cw + " " + ccw);}console.log(out.join("\n"));
JavaMain.java · 46 lines
import java.io.*;import java.util.*;public class Main { static long[] P, Q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 static long forward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); } // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 static long backward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); P = new long[n + 1]; Q = new long[n + 1]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { long t = Long.parseLong(st.nextToken()); P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); int s = Integer.parseInt(st.nextToken()) - 1; int k = Integer.parseInt(st.nextToken()); long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.append(cw).append(' ').append(ccw).append('\n'); } System.out.print(out); }}
C#Main.cs · 48 lines
using System;using System.Text;class Program{ static long[] P, Q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 static long Forward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); } // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 static long Backward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); } static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] t = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); P = new long[n + 1]; Q = new long[n + 1]; for (int i = 0; i < n; i++) { P[i + 1] = P[i] + t[i]; Q[i + 1] = Q[i] + i * t[i]; } var sb = new StringBuilder(); for (int i = 0; i < q; i++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int s = int.Parse(p[0]) - 1, k = int.Parse(p[1]); long cw, ccw; if (s + k <= n) cw = Forward(s, s + k, k - 1); else cw = Forward(s, n, k - 1) + Forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = Backward(s - k + 1, s + 1, k - 1); else ccw = Backward(0, s + 1, k - 1) + Backward(n - (k - s - 1), n, k - 1 - (s + 1)); sb.Append(cw).Append(' ').Append(ccw).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 40 lines
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 vector<long long> P(n + 1, 0), Q(n + 1, 0); for (int i = 0; i < n; i++) { long long t; cin >> t; P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 auto forward = [&](int a, int b, int c) -> long long { long long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); }; // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 auto backward = [&](int a, int b, int c) -> long long { long long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); }; while (q--) { int s, k; cin >> s >> k; s--; long long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); cout << cw << ' ' << ccw << '\n'; } return 0;}
Cmain.c · 39 lines
#include <stdio.h>/* P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 */static long long P[9001], Q[9001];/* 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 */static long long forward(int a, int b, int c) { long long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp);}/* 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 */static long long backward(int a, int b, int c) { long long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) { long long t; if (scanf("%lld", &t) != 1) return 0; P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } for (int i = 0; i < q; i++) { int s, k; if (scanf("%d %d", &s, &k) != 2) return 0; s--; long long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); printf("%lld %lld\n", cw, ccw); } return 0;}
Craykonmain.cray · 52 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];t = Console.ReadNumbers();// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합P = NewList(n + 1, 0);Q = NewList(n + 1, 0);for (i = 0; i < n; i++){ P[i + 1] = P[i] + t[i]; Q[i + 1] = Q[i] + i * t[i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다앞으로(a, b, c){ dp = P[b] - P[a]; return c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다뒤로(a, b, c){ dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}for (i = 0; i < q; i++){ 줄 = Console.ReadNumbers(); s = 줄[0] - 1; k = 줄[1]; 시계 = 0; 반시계 = 0; if (s + k <= n) { 시계 = 앞으로(s, s + k, k - 1); } else { 시계 = 앞으로(s, n, k - 1) + 앞으로(0, s + k - n, k - 1 - (n - s)); } if (k <= s + 1) { 반시계 = 뒤로(s - k + 1, s + 1, k - 1); } else { 반시계 = 뒤로(0, s + 1, k - 1) + 뒤로(n - (k - s - 1), n, k - 1 - (s + 1)); } Console.WriteLine(시계 + " " + 반시계);}