There is a weather record for n days.
On day i the amount of sunshine was s_i and the amount of rain was w_i.
Persimmons are dried over some consecutive days, and they dry well only if the total sunshine over those days is at least S and the total rain is at most R.
Among the ways to choose a first day and a last day, call a way in which the persimmons dry well a good period. Drying for a single day is also a period.
You are given q questions.
For each question "S R", print on one line the number of good periods, the number of days in the shortest good period, and the number of the day that period starts on, separated by single spaces.
If there are several shortest good periods, choose the one that starts earliest.
If there is no good period, print 0 0 0.
For the first question "5 3" in example 1 there are four good periods, days 4–5, day 5, days 4–6 and days 5–6, and the shortest is day 5 alone.
Input
The first line gives n and q separated by one space. The second line gives s_1, …, s_n and the third line gives w_1, …, w_n, separated by single spaces. Each of the next q lines gives S and R separated by one space. 1 ≤ n ≤ 9,000, 1 ≤ q ≤ 150, 0 ≤ s_i, w_i ≤ 10^9, 0 ≤ S, R ≤ 10^13 (all integers, given as plain digits without commas)
Output
For each question one line with the number of good periods, the number of days in the shortest good period, and the number of the day it starts on. If there is no good period, 0 0 0
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
Fix the last day r. As the first day moves earlier, both the sunshine total and the rain total only grow (the values are 0 or more). So the rain condition holds only when the first day is some day lo or later, and the sunshine condition holds only when it is some day hi or earlier. The good periods ending on r are the hi - lo + 1 ones whose first day is from lo to hi, and the shortest of them starts on hi. When r grows by one day, lo and hi only move forward. So each of the three pointers (r, lo, hi) passes from the beginning to the end just once, and one question finishes in time proportional to n. The totals are not added up again either: you carry the rain total of lo..r and the sunshine total of hi..r, adding and removing one day at a time. The solutions in the eight languages look almost the same. C, C++, Java, C#, JavaScript and TypeScript can subtract and move the pointer in one line, as in rainSum -= rain[lo++]; Python and Craykon cannot use ++ inside an expression, so they write it in two lines. Trap one: if you look at every period by extending the last day one at a time for each first day, you look at about 40 million periods per question and about 6 billion in all. There is an input with no rain at all, so you cannot stop early either. A Python solution written this way did not finish in time, and a C solution written the same way took 12 seconds on the largest input on this computer. Trap two: when lo is after hi, no good period ends on r. Adding hi - lo + 1 without checking lo <= hi adds a negative number. The first question of example 1 gives 2 instead of 4, and the second gives -1 1 3 instead of 0 0 0. Trap three: without hi < r in the loop that moves hi, when S is 0 hi goes past r and counts periods with no days in them. For the third question "0 1" of example 1, JavaScript prints 12 -1 3 instead of 5 1 1. JavaScript only gives undefined when you read past the end of a list, so it is silently wrong; Python stops with IndexError, and Java and C# stop with an exception. In C and C++ what happens is not defined. Trap four: when there are several shortest periods you must choose the one that starts earliest. Because r grows from the front, comparing with < keeps the one found first. Comparing with <= makes the starting day 6 instead of 1 for the third question of example 1. Trap five: the totals grow up to 9 × 10^12. Java, C#, C and C++ must keep the totals, S and R in long/long long. Keeping the totals in a Java int turns 3 billion into -1294967296 for the first question of example 2, which gives 0 0 0 instead of 1 3 1. Python integers have no size limit, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53, so they are right as they are. The number of good periods is at most about 40.5 million, so it fits in an int.
Pythonmain.py · 44 lines
import sysdef solve(n, sun, rain, need, limit): """햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날).""" count = 0 best_len = best_start = 0 lo = 0 # 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0 # 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) rain_sum = 0 # lo..r의 비 합 sun_sum = 0 # hi..r의 햇볕 합 for r in range(n): rain_sum += rain[r] while rain_sum > limit: rain_sum -= rain[lo] lo += 1 sun_sum += sun[r] while hi < r and sun_sum - sun[hi] >= need: sun_sum -= sun[hi] hi += 1 # 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if sun_sum >= need and lo <= hi: count += hi - lo + 1 if best_len == 0 or r - hi + 1 < best_len: best_len = r - hi + 1 best_start = hi + 1 return count, best_len, best_startdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) sun = [int(x) for x in data[2:2 + n]] rain = [int(x) for x in data[2 + n:2 + 2 * n]] out = [] pos = 2 + 2 * n for _ in range(q): need, limit = int(data[pos]), int(data[pos + 1]) pos += 2 out.append("%d %d %d" % solve(n, sun, rain, need, limit)) print("\n".join(out))main()
JavaScriptmain.js · 37 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun = data.slice(2, 2 + n);const rain = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need, limit) { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 38 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun: number[] = data.slice(2, 2 + n);const rain: number[] = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need: number, limit: number): [number, number, number] { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out: string[] = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 45 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] sun = new long[n]; long[] rain = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) sun[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) rain[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(in.readLine()); long need = Long.parseLong(st.nextToken()); long limit = Long.parseLong(st.nextToken()); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } out.append(count).append(' ').append(bestLen).append(' ').append(bestStart).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 lines
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] sun = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] rain = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long need = long.Parse(p[0]), limit = long.Parse(p[1]); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } sb.Append(count).Append(' ').Append(bestLen).Append(' ').Append(bestStart).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 39 lines
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long> sun(n), rain(n); for (auto& v : sun) cin >> v; for (auto& v : rain) cin >> v; while (q--) { long long need, limit; cin >> need >> limit; int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long long rainSum = 0; // lo..r의 비 합 long long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } cout << count << ' ' << bestLen << ' ' << bestStart << '\n'; } return 0;}
Cmain.c · 36 lines
#include <stdio.h>static long long sun[9000], rain[9000];int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &sun[i]) != 1) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &rain[i]) != 1) return 0; for (int k = 0; k < q; k++) { long long need, limit; if (scanf("%lld %lld", &need, &limit) != 2) return 0; int count = 0, best_len = 0, best_start = 0; int lo = 0; /* 비 합이 limit 이하가 되는 가장 이른 시작 날 */ int hi = 0; /* 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) */ long long rain_sum = 0; /* lo..r의 비 합 */ long long sun_sum = 0; /* hi..r의 햇볕 합 */ for (int r = 0; r < n; r++) { rain_sum += rain[r]; while (rain_sum > limit) rain_sum -= rain[lo++]; sun_sum += sun[r]; while (hi < r && sun_sum - sun[hi] >= need) sun_sum -= sun[hi++]; /* 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 */ if (sun_sum >= need && lo <= hi) { count += hi - lo + 1; if (best_len == 0 || r - hi + 1 < best_len) { best_len = r - hi + 1; best_start = hi + 1; } } } printf("%d %d %d\n", count, best_len, best_start); } return 0;}
Craykonmain.cray · 45 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];볕 = Console.ReadNumbers();비 = Console.ReadNumbers();for (k = 0; k < q; k++){ 줄 = Console.ReadNumbers(); need = 줄[0]; limit = 줄[1]; 센수 = 0; 짧은길이 = 0; 짧은시작 = 0; lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0; // 볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) 비합 = 0; // lo..r의 비 합 볕합 = 0; // hi..r의 볕 합 for (r = 0; r < n; r++) { 비합 = 비합 + 비[r]; while (비합 > limit) { 비합 = 비합 - 비[lo]; lo = lo + 1; } 볕합 = 볕합 + 볕[r]; while (hi < r && 볕합 - 볕[hi] >= need) { 볕합 = 볕합 - 볕[hi]; hi = hi + 1; } // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (볕합 >= need && lo <= hi) { 센수 = 센수 + hi - lo + 1; if (짧은길이 == 0 || r - hi + 1 < 짧은길이) { 짧은길이 = r - hi + 1; 짧은시작 = hi + 1; } } } Console.WriteLine(센수 + " " + 짧은길이 + " " + 짧은시작);}