문제 5251 · 메가 IV
만원 버스의 안정 구간
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1000ms / 테스트 (언어별 보정은 아래 표) | 메모리: 측정하지 않음(브라우저 채점) | 0 | 0 | 0 | 0.00% |
문제
한 도시의 직선 버스 노선에는 N개의 정류장이 1번부터 N번까지 차례로 놓여 있다. 버스가 i번 정류장에 정차하면 차내 승객 수가 a_i명만큼 변한다. a_i가 양수이면 승객이 순증가한 것이고, 음수이면 순감소한 것이며, 0이면 변화가 없다는 뜻이다. 운영팀은 연속한 정류장 구간 [l, r] (1 ≤ l ≤ r ≤ N)을 하나 고르고, 그 구간에 속한 정류장들의 변화량을 모두 더한 값 a_l + a_{l+1} + … + a_r 을 그 구간의 승객 증감이라고 부른다. 승객 증감이 L 이상 R 이하인 구간을 안정 구간이라고 한다. 길이가 1인 구간도 하나의 구간이며, 시작 번호나 끝 번호가 하나라도 다르면 서로 다른 구간으로 센다. 운영팀은 노선 전체에서 안정 구간이 모두 몇 개인지 알고 싶다. 안정 구간의 개수를 구하는 프로그램을 작성하라. 안정 구간이 하나도 없으면 0을 출력한다. 답은 최대 약 2×10^10 이므로 64비트 정수형이 필요할 수 있다.
입력
첫째 줄에 정류장 수 N, 정수 L, 정수 R이 공백으로 구분되어 주어진다. 둘째 줄에 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, |a_i| ≤ 10^9, -10^15 ≤ L ≤ R ≤ 10^15 이며 모든 값은 정수이다.
출력
안정 구간의 개수를 한 줄에 출력한다.
예제 입력 1
4 1 3 1 -2 3 0
예제 출력 1
7
예제 입력 2
3 0 0 0 0 0
예제 출력 2
6
예제 입력 3
1 5 5 4
예제 출력 3
0
힌트 펼치기
- 구간 합은 두 누적 합의 차이로 쓸 수 있다.
- 누적 합 P_0=0, P_1, …, P_N에 대해 i<j 이고 L ≤ P_j − P_i ≤ R 인 쌍의 수를 센다.
- 각 j마다 P_j − R ≤ P_i ≤ P_j − L 인 앞쪽 값의 개수를 값 압축과 펜윅 트리로 센다.
관련 서재 장
알고리즘 분류
누적 합정렬구간 세기풀이 작성
연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.
이 브라우저의 연습 기록
언어별 제한
테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.
| 언어 | 엔진(버전) | 시간 제한 | 메모리 |
|---|---|---|---|
| javascript | 사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름) | 1000ms / 테스트 | 측정하지 않음(브라우저 채점) |
| python | Pyodide 314.0.7 (CPython 3.14 WASM) | 5000ms / 테스트 | 측정하지 않음(브라우저 채점) |