Cheapest Numbers
Time: 3.0 s Memory: 1024 MB
-
Givet är en lista med $N$ heltal. Du ska svara på $Q$ frågor av formen "vad är största antalet tal i intervallet $[l,r]$ du kan välja så att deras summa är mindre eller lika med $V$".
Indata
Den första raden innehåller två heltal $N,Q$ ($1 \leq N,Q \leq 10^5$).
Den andra raden innehåller $N$ heltal, värdena i listan. Alla talen är mindre än $10^9$.
Därefter följer $Q$ rader som vardera innehåller tre heltal $l, r, V$ ($0 \leq l \leq r \leq N-1$, $0 \leq V \leq 10^9$), den vänstra respektive högra ändpunkten på intervallet och största giltiga summan.
Utdata
För varje fråga, skriv ut antalet tal du kan välja i intervallet $[l,r]$ så att deras summa är mindre eller lika med $V$.
Poängsättning
Din lösning kommer att testas på flera testfall. För att lösa problemet måste du klara alla testfall.
Sample Input 1 Sample Output 1 3 5 1 2 3 0 2 0 0 2 2 0 2 7 2 2 2 1 1 3
0 1 3 0 1
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - A Count Numbers
- B Count Numbers 2
- C Substring Equality
- D Cheapest Numbers
- E Sneetches