# PBinfo #2443 – cb2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări. Fiecare interogare este dată de o pereche (x, s): care este indicele maxim p cu proprietatea că a[i] ≤ x, pentru orice i=1..p și în plus a[1] + a[2] + ... + a[p] ≤ s? 

Cerința
Trebuie să răspundeți la fiecare din cele Q întrebări.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele șirului. Apoi se citește valoarea Q și la final se citesc Q perechi de forma (x, s) reprezentând întrebările. 

Date de ieșire
Programul va afișa pe câte o linie la ecran Q valori reprezentând răspunsurile la întrebări.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ Q ≤ 100.000
1 ≤ a[i] ≤ 1.000 pentru orice i=1..n
pentru fiecare întrebare, 1 ≤ x, s ≤ 1.000.000.000

Exemplu:
Intrare

9
5 3 1 7 4 9 8 2 6
6
8 10
4 20
6 20
6 8
10 100
10 20
Ieșire

3
0
3
2
9
5
Explicație
La prima întrebare, x=8, s=10. Indicele maxim este 3 pentru că primele trei valori din șir sunt mai mici sau egale cu 8, iar 5 + 3 + 1 ≤ 10.
La a doua întrebare, răspunsul este 0 deoarece primul număr din șir este 5 care este mai mare decât x=4.
La a cincea întrebare, x=10 și s=100. Răspunsul este chiar lungimea șirului.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100001], s[100001], maxim[100001];
int cautarebinara(int a[], int n, int val) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (val < a[mid]) dr = mid - 1;
        else st = mid + 1;
    } return dr;
}
int main() {
    int n, Q, l, r; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] > maxim[i - 1]) maxim[i] = a[i];
        else maxim[i] = maxim[i-1];
    } cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> l >> r;
        int rez1 = cautarebinara(maxim, n, l);
        int rez2 = cautarebinara(s, n, r);
        cout << min(rez1, rez2) << "\n";
    } return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2443)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2443/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2443/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)