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]);}