Campfires that cool with distance and the warmth of the campsite
A campsite has n tent spots in a row, numbered 1 to n.
m campfires are lit. One spot may hold several campfires.
A campfire of strength s at spot p warms spot x by s − |x − p|. If this value is 0 or less, the spot gets no warmth from this campfire.
That is, spot p gets s, its two neighbours get s − 1, one step farther gets s − 2, dropping by 1 per step.
There are no spots left of 1 or right of n, so warmth going that way is lost.
The warmth of a spot is the sum of what every campfire gives it.
On the first line print the warmth of the warmest spot and its number. If several spots tie, choose the smallest number.
Then answer q questions in order. The answer to question "l r" is the sum of warmth over spots l through r.
Input
The first line has n, m, q; the next m lines give a campfire's "p s"; the next q lines give a question's "l r", separated by single spaces. 1 ≤ n ≤ 9,000, 1 ≤ m ≤ 10,000, 1 ≤ q ≤ 5,000, 1 ≤ p ≤ n, 1 ≤ s ≤ 1,000,000, 1 ≤ l ≤ r ≤ n. All are integers
Output
On the first line print the warmth of the warmest spot and its number separated by one space. On the next q lines print the answers, one per line. Plain digits, no commas
Example 1 · stdin
7 2 2
2 3
6 2
1 7
3 5
stdout
3 2
12
4
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 every spot each campfire reaches takes m × n = 90 million steps, too slow for Python and Craykon. Use prefix sums in three layers. One campfire's warmth is a mountain that climbs +1 per step from the left and falls −1 per step after p, so its 'slope' is +1 on p−s+1 … p and −1 on p+1 … p+s. A range add on the slope touches only two cells of a difference array (the method of P0259); after collecting all, one accumulation gives the slope, a second gives the warmth, and a third gives prefix sums that answer a range with one subtraction. Example: the warmth is 2 3 2 1 1 2 1 and spots 3–5 sum to 2 + 1 + 1 = 4. Trap one: the climb's first spot p − s + 1 can be below 1. Python's dd[-3] silently changes the third cell from the end, JavaScript/TypeScript quietly create a property named "-3" on the array, C/C++ touch memory outside the array, and Java, C# and Craykon stop with a runtime error. Trap two: just clamping the start to spot 1 is still wrong — spot 1 has already climbed to s − (p − 1), so add that height separately to the slope at spot 1. A fall running off the right just drops what lies past n. Trap three: accumulating only once makes a 'flat range add', not a mountain. Trap four: a range sum is prefix[r] − prefix[l − 1]; subtracting prefix[l] loses spot l. Trap five: >= for the warmest spot keeps the larger number. Trap six: one spot's warmth reaches 10^10 and sums about 9×10^13, so use long long in C/C++ and long in Java/C# (a 32-bit int holds about 2.1 billion). Python integers don't overflow, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53 (about 9×10^15). Craykon makes a zero-filled list with NewList(n + 3, 0) and clamps with Mathf.Max and Mathf.Min (a Craykon list holds at most 10,000 items).
Pythonmain.py · 44 lines
import sysdata = sys.stdin.buffer.read().split()n, m, q = int(data[0]), int(data[1]), int(data[2])# dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다)dd = [0] * (n + 3)pos = 3for _ in range(m): p, s = int(data[pos]), int(data[pos + 1]) pos += 2 # 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 first = s - (p - 1) if first > 0: dd[1] += first dd[2] -= first lo = max(2, p - s + 1) # 오르막: lo..p에서 한 칸에 +1 if lo <= p: dd[lo] += 1 dd[p + 1] -= 1 hi = min(n, p + s) # 내리막: p+1..hi에서 한 칸에 -1 if p + 1 <= hi: dd[p + 1] -= 1 dd[hi + 1] += 1prefix = [0] * (n + 1) # prefix[x] = 1..x번 자리의 따뜻함의 합slope = 0warm = 0best = -1best_at = 0for x in range(1, n + 1): slope += dd[x] # 첫 번째 누적: 기울기 warm += slope # 두 번째 누적: 따뜻함 prefix[x] = prefix[x - 1] + warm # 세 번째 누적: 구간 합을 위한 누적 합 if warm > best: best = warm best_at = xout = [f"{best} {best_at}"]for _ in range(q): l, r = int(data[pos]), int(data[pos + 1]) pos += 2 out.append(str(prefix[r] - prefix[l - 1]))print("\n".join(out))
JavaScriptmain.js · 49 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다)const dd = new Array(n + 3).fill(0);let pos = 3;for (let i = 0; i < m; i++) { const p = data[pos++]; const s = data[pos++]; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 const first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } const lo = Math.max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } const hi = Math.min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; }}const prefix = new Array(n + 1).fill(0); // prefix[x] = 1..x번 자리의 따뜻함의 합let slope = 0;let warm = 0;let best = -1;let bestAt = 0;for (let x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; }}const out = [best + " " + bestAt];for (let i = 0; i < q; i++) { const l = data[pos++]; const r = data[pos++]; out.push(prefix[r] - prefix[l - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 51 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다)const dd: number[] = new Array<number>(n + 3).fill(0);let pos = 3;for (let i = 0; i < m; i++) { const p: number = data[pos++]; const s: number = data[pos++]; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 const first: number = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } const lo: number = Math.max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } const hi: number = Math.min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; }}const prefix: number[] = new Array<number>(n + 1).fill(0); // prefix[x] = 1..x번 자리의 따뜻함의 합let slope = 0;let warm = 0;let best = -1;let bestAt = 0;for (let x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; }}const out: string[] = [`${best} ${bestAt}`];for (let i = 0; i < q; i++) { const l: number = data[pos++]; const r: number = data[pos++]; out.push(String(prefix[r] - prefix[l - 1]));}console.log(out.join("\n"));
JavaMain.java · 55 lines
import java.io.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; st.nextToken(); int q = (int) st.nval; // dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다) long[] dd = new long[n + 3]; for (int i = 0; i < m; i++) { st.nextToken(); int p = (int) st.nval; st.nextToken(); int s = (int) st.nval; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 int first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } int lo = Math.max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } int hi = Math.min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; } } long[] prefix = new long[n + 1]; // 10^14까지 가서 int로는 넘친다 long slope = 0, warm = 0, best = -1; int bestAt = 0; for (int x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; } } StringBuilder out = new StringBuilder(); out.append(best).append(' ').append(bestAt).append('\n'); for (int i = 0; i < q; i++) { st.nextToken(); int l = (int) st.nval; st.nextToken(); int r = (int) st.nval; out.append(prefix[r] - prefix[l - 1]).append('\n'); } System.out.print(out); }}
C#Main.cs · 64 lines
using System;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), m = int.Parse(data[1]), q = int.Parse(data[2]); // dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다) var dd = new long[n + 3]; int pos = 3; for (int i = 0; i < m; i++) { int p = int.Parse(data[pos++]); int s = int.Parse(data[pos++]); // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 int first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } int lo = Math.Max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } int hi = Math.Min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; } } var prefix = new long[n + 1]; // 10^14까지 가서 int로는 넘친다 long slope = 0, warm = 0, best = -1; int bestAt = 0; for (int x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; } } var sb = new StringBuilder(); sb.Append(best).Append(' ').Append(bestAt).Append('\n'); for (int i = 0; i < q; i++) { int l = int.Parse(data[pos++]); int r = int.Parse(data[pos++]); sb.Append(prefix[r] - prefix[l - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 55 lines
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; // dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다) vector<long long> dd(n + 3, 0); for (int i = 0; i < m; i++) { int p, s; cin >> p >> s; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 int first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } int lo = max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } int hi = min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; } } vector<long long> prefix(n + 1, 0); // 10^14까지 가서 int로는 넘친다 long long slope = 0, warm = 0, best = -1; int bestAt = 0; for (int x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; } } cout << best << ' ' << bestAt << '\n'; for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; cout << prefix[r] - prefix[l - 1] << '\n'; } return 0;}
Cmain.c · 51 lines
#include <stdio.h>#define MAXN 9000static long long dd[MAXN + 3]; /* dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지 */static long long prefix[MAXN + 1]; /* prefix[x] = 1..x번 자리의 따뜻함의 합(10^14까지) */int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 1; for (int i = 0; i < m; i++) { int p, s; scanf("%d %d", &p, &s); /* 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 */ int first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } int lo = p - s + 1 > 2 ? p - s + 1 : 2; /* 오르막: lo..p에서 한 칸에 +1 */ if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } int hi = p + s < n ? p + s : n; /* 내리막: p+1..hi에서 한 칸에 -1 */ if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; } } long long slope = 0, warm = 0, best = -1; int bestAt = 0; for (int x = 1; x <= n; x++) { slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; } } printf("%lld %d\n", best, bestAt); for (int i = 0; i < q; i++) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", prefix[r] - prefix[l - 1]); } return 0;}
Craykonmain.cray · 56 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];// dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다)dd = NewList(n + 3, 0);for (i = 0; i < m; i++){ 줄 = Console.ReadNumbers(); p = 줄[0]; s = 줄[1]; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 first = s - (p - 1); if (first > 0) { dd[1] += first; dd[2] -= first; } lo = Mathf.Max(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 if (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } hi = Mathf.Min(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 if (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; }}prefix = NewList(n + 1, 0); // prefix[x] = 1..x번 자리의 따뜻함의 합slope = 0;warm = 0;best = -1;bestAt = 0;for (x = 1; x <= n; x++){ slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; if (warm > best) { best = warm; bestAt = x; }}Console.WriteLine(best + " " + bestAt);for (i = 0; i < q; i++){ 줄 = Console.ReadNumbers(); Console.WriteLine(prefix[줄[1]] - prefix[줄[0] - 1]);}