야영장에 텐트 자리 n개가 한 줄로 있고, 1번부터 n번까지 번호가 붙어 있다.
모닥불 m개를 피운다. 한 자리에 모닥불이 여러 개 있을 수 있다.
p번 자리에 세기 s로 피운 모닥불은 x번 자리를 s − |x − p|만큼 따뜻하게 한다. 이 값이 0 이하이면 그 자리는 이 모닥불로 따뜻해지지 않는다.
곧 p번 자리는 s, 그 양옆은 s − 1, 한 칸 더 멀면 s − 2처럼 한 칸 멀어질 때마다 1씩 줄어든다.
1번보다 왼쪽이나 n번보다 오른쪽에는 자리가 없으니 그쪽으로 나간 온기는 버려진다.
한 자리의 따뜻함은 모든 모닥불이 그 자리에 주는 값의 합이다.
첫 줄에 가장 따뜻한 자리의 따뜻함과 그 자리 번호를 출력하라. 그런 자리가 여러 개이면 번호가 가장 작은 것을 고른다.
이어서 질문 q개에 차례대로 답하라. 질문 "l r"의 답은 l번부터 r번 자리까지 따뜻함의 합이다.
입력
첫 줄에 n, m, q, 다음 m줄에 모닥불의 "p s", 다음 q줄에 질문의 "l r"이 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 9,000, 1 ≤ m ≤ 10,000, 1 ≤ q ≤ 5,000, 1 ≤ p ≤ n, 1 ≤ s ≤ 1,000,000, 1 ≤ l ≤ r ≤ n. 모두 정수다
출력
첫 줄에 가장 따뜻한 자리의 따뜻함과 자리 번호를 빈칸 하나로 띄워 출력한다. 다음 q줄에 질문의 답을 한 줄에 하나씩 출력한다. 쉼표 없이 숫자만 쓴다
예시 1 · stdin
7 2 2
2 3
6 2
1 7
3 5
stdout
3 2
12
4
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
모닥불마다 닿는 자리를 하나씩 더하면 m × n = 9천만 번이라 Python·크레이콘에는 느려요. 누적 합을 세 겹으로 써요. 모닥불 하나의 온기는 왼쪽에서 한 칸에 +1씩 오르다가 p를 지나면 −1씩 내려가는 산 모양이니, '기울기'는 구간 p−s+1 … p에서 +1, p+1 … p+s에서 −1이에요. 기울기의 구간 더하기는 차이 배열로 양 끝 두 칸만 고치면 되고(P0259의 방법), 다 모은 뒤 한 번 누적하면 기울기, 또 누적하면 따뜻함, 한 번 더 누적하면 구간 합을 뺄셈 한 번으로 구하는 누적 합이 돼요. 예시: 따뜻함은 2 3 2 1 1 2 1이고 3~5번의 합은 2 + 1 + 1 = 4예요. 함정 하나: 오르막이 시작하는 자리 p − s + 1이 1보다 작을 수 있어요. Python은 dd[-3]이 오류 없이 뒤에서 셋째 칸을 고치고, JavaScript·TypeScript는 배열에 "-3"이라는 속성을 조용히 만들고, C·C++은 배열 밖 메모리를 건드리고, Java·C#·크레이콘은 실행 오류로 멈춰요. 함정 둘: 그렇다고 시작을 1번으로 당기기만 하면 틀려요 — 1번 자리는 이미 s − (p − 1)만큼 올라와 있으니 그 높이를 1번 자리의 기울기에 따로 더해야 해요. 오른쪽으로 나간 내리막은 n번 뒤를 버리면 돼요. 함정 셋: 누적을 한 번만 하면 '평평한 구간 더하기'가 되어 산 모양이 안 나와요. 함정 넷: 구간 합은 prefix[r] − prefix[l − 1]이에요. prefix[l]을 빼면 l번 자리가 빠져요. 함정 다섯: 가장 따뜻한 자리를 >=로 바꾸면 번호가 큰 자리가 남아요. 함정 여섯: 한 자리의 따뜻함은 10^10, 합은 약 9×10^13까지 가니 C·C++은 long long, Java·C#은 long이에요(32비트 int는 약 21억까지). Python 정수는 넘치지 않고, JavaScript·TypeScript·크레이콘의 수는 2^53(약 9×10^15)까지 정확해요. 크레이콘은 새목록(n + 3, 0)으로 0이 든 목록을 만들고 수학.큰수·수학.작은수로 범위를 잘라요(크레이콘 목록은 10,000칸까지 담아요).
Pythonmain.py · 44 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];// dd[x]: x번 자리에서 '기울기'가 얼마나 바뀌는지(두 번 누적하면 따뜻함이 된다)dd = 새목록(n + 3, 0);반복 (i = 0; i < m; i++){ 줄 = 콘솔.수들읽기(); p = 줄[0]; s = 줄[1]; // 왼쪽 비탈이 1번 자리 밖에서 시작하면, 1번 자리는 이미 s - (p - 1)만큼 따뜻하다 first = s - (p - 1); 만약 (first > 0) { dd[1] += first; dd[2] -= first; } lo = 수학.큰수(2, p - s + 1); // 오르막: lo..p에서 한 칸에 +1 만약 (lo <= p) { dd[lo] += 1; dd[p + 1] -= 1; } hi = 수학.작은수(n, p + s); // 내리막: p+1..hi에서 한 칸에 -1 만약 (p + 1 <= hi) { dd[p + 1] -= 1; dd[hi + 1] += 1; }}prefix = 새목록(n + 1, 0); // prefix[x] = 1..x번 자리의 따뜻함의 합slope = 0;warm = 0;best = -1;bestAt = 0;반복 (x = 1; x <= n; x++){ slope += dd[x]; warm += slope; prefix[x] = prefix[x - 1] + warm; 만약 (warm > best) { best = warm; bestAt = x; }}콘솔.쓰기(best + " " + bestAt);반복 (i = 0; i < q; i++){ 줄 = 콘솔.수들읽기(); 콘솔.쓰기(prefix[줄[1]] - prefix[줄[0] - 1]);}