기간별 손익

100점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

한 가게가 문을 연 날부터 N일 동안의 손익을 날짜 순으로 적어 두었다. 1일차부터 N일차까지의 각 날에 대하여, 그 날 남긴 금액이 정수로 적혀 있다. 값이 양수면 그만큼 남긴 것이고, 음수면 그만큼 손해를 본 것이다.

회계 담당자는 이 기록을 보고 M번의 정산을 한다. 각 정산은 두 날짜 i와 j로 이루어지며, i일차부터 j일차까지의 손익을 모두 더한 값을 구하는 작업이다. i와 j가 같으면 그 하루의 손익만 보는 것이다.

손익 기록과 M번의 정산 정보가 주어졌을 때, 각 정산의 결과를 차례대로 계산하는 프로그램을 작성하여라.

예를 들어 N=5일 동안의 손익이 다음의 표와 같다고 해보자.

날짜	1	2	3	4	5
손익	5	4	3	2	1

이후에 M=3번의 정산에 대한 정보가 차례대로 [1, 3], [2, 4], [5, 5]라고 가정하자. 각 정산의 결과를 표로 정리하면 다음과 같다.

정산	1번	2번	3번
시작 날짜	1	2	5
끝 날짜	3	4	5
더한 손익	5와 4와 3	4와 3과 2	1
결과	12	9	1

정산이 최대 10만 번이고 기록한 날도 최대 10만 일이므로, 정산마다 그 기간의 손익을 처음부터 다시 더하면 시간이 모자란다. 1일차부터 각 날까지의 손익을 미리 더해 두면 정산 한 번을 뺄셈 한 번으로 끝낼 수 있다. 위 예시에서 1일차부터 각 날까지 더한 값을 표로 정리하면 다음과 같다.

날짜	1	2	3	4	5
1일차부터 더한 값	5	9	12	14	15

2일차부터 4일차까지의 손익은 4일차까지 더한 값 14에서 1일차까지 더한 값 5를 빼면 9로 바로 나온다. 따라서 이 경우의 정답은 차례대로 12, 9, 1이다.

입출력 예시

예시 1

입력

출력

12
9
1

예시 2

입력

출력

-558
-159

예시 3

입력

출력

-38

입력 조건

가장 먼저 첫째 줄에 기록한 날의 수 N이 주어진다. N은 1 이상 100,000 이하의 자연수다.
이어서 둘째 줄에 1일차부터 N일차까지의 손익이 공백으로 구분되어 한 줄에 주어진다. 각 날의 손익은 절댓값이 1,000 이하인 정수다.
이어서 셋째 줄에 정산의 횟수 M이 주어진다. M은 1 이상 100,000 이하의 자연수다.
이어서 M개의 줄에 걸쳐 각 정산의 정보가 주어진다. 각 줄에는 시작 날짜 i와 끝 날짜 j가 공백으로 구분되어 주어진다. i는 1 이상 N 이하의 자연수이고, j는 i 이상 N 이하의 자연수다.
입력 전체의 크기는 최대 약 1.6MB다. 줄의 수가 최대 100,003개이므로, 입력 전체를 한 번에 읽어서 줄 단위로 나누는 방식으로 처리해야 한다.

출력 조건

M번의 정산 결과를 한 줄에 하나씩 차례대로 출력한다. 이때 각 정산 결과 뒤에 줄바꿈을 하나씩 붙여서 하나의 문자열로 이어 붙인 다음, 그 문자열을 한 번에 출력한다. 그래서 마지막 정산 결과 뒤에도 줄바꿈이 하나 더 붙고, 출력의 맨 끝에 빈 줄이 하나 남는다. 정산이 M번이면 출력에 들어가는 줄바꿈은 M+1개다.

요구사항

출력의 맨 끝에 빈 줄이 하나 남아야 합니다. 정산 결과 M개 뒤에 줄바꿈이 M+1개 들어갑니다
손익은 음수일 수 있고, 기간의 합도 음수일 수 있습니다
정산 정보는 항상 i가 j보다 작거나 같은 형태로 주어집니다
i와 j가 같은 정산은 그 하루의 손익만 보는 것입니다
정산이 최대 10만 번이므로 정산마다 기간을 다시 더하면 시간이 모자랍니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

-38

-558
-159

12
9
1

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 67ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.