時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
給定正整數序列 w。對每個詢問 l、r、a、b，尋找區間 [l,r] 中最小的索引 k，使 w[l] 到 w[k] 的總和至少為整段總和的 a/(a+b)。也就是切點之前的累積比例嚴格小於目標，而包含切點後的比例大於或等於目標。由於元素皆為正數，答案唯一。
輸入格式
第一行為 N、M，1 ≤ N,M ≤ 100000。第二行為 N 個 wᵢ，1 ≤ wᵢ ≤ 10000。接下來 M 行各有 l、r、a、b，滿足 1 ≤ l ≤ r ≤ N，1 ≤ a ≤ b ≤ 10。
輸出格式
每個詢問各輸出一行，內容為分割點 k 的索引。
範例測資
範例輸入 1
6 1 2 2 6 3 1 5 1 6 1 1
範例輸出 1
3
範例輸入 2
12 3 1 4 2 3 6 7 1 9 9 8 10 6 4 10 1 6 1 6 1 10 3 11 6 8
範例輸出 2
5 2 8
請先登入後再提交程式碼
討論與題解
載入討論區…