# PBinfo #2510 – vsecvente – Rezolvare C++

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

## Enunț

Considerăm un șir de numere naturale nenule a[1], a[2], …, a[n]. În acest șir o V-secvență este o secvență maximală de forma a[x], a[x+1], …, a[y] cu proprietatea că toate numerele din secvență au valori mai mici sau egale cu V. Este maximală pentru că nu poate fi extinsă spre stânga sau spre dreapta. De exemplu, șirul a = 2, 2, 6, 4, 3, 14, 7, 4, 3, 36 are două 7-secvențe: 2, 2, 6, 4, 3 și 7, 4, 3. De asemenea, șirul are trei 4-secvențe: 2,2; 4,3; 4,3. De notat că 2,6,4,3 nu este 7-secvență, deoarece poate fi extinsă la capătul său stâng cu numărul 2.

Cerința
Pentru un șir de numere dat, trebuie să răspundeți la Q întrebări notate V[1], V[2],…, V[Q]. Pentru fiecare întrebare i, dată prin numărul natural V[i], trebuie să aflați câte V[i]-secvențe sunt în șir.

Date de intrare
Fișierul de intrare vsecvente.in conține pe prima linie numărul natural N. Pe a doua linie, separate prin câte un spațiu, se află cele N elemente ale șirului. Pe a treia linie se află un singur număr natural Q reprezentând numărul de întrebări. Pe a patra linie, se află șirul de Q numere naturale V[1], V[2],…, V[Q], separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire vsecvente.out va conține Q linii. Linia a i-a va conține numărul de V[i]-secvențe aflate în șir.

Restricții și precizări

1 ≤ toate numerele din fișierul de intrare ≤ 1 100 000
Pentru teste totalizând 75 puncte, 1 ≤ toate numerele din fișierul de intrare ≤ 550 000

Exemplu:
vsecvente.in

10
2 2 6 4 3 14 7 4 3 36
3
7 1 4
vsecvente.out

2
0
3
Explicație
Sunt trei întrebări:
- sunt două 7-secvențe: 2 2 6 4 3 și 7 4 3.
- nu există nicio 1-secvență.
- există trei 4-secvențe: 2 2;  4 3 și 4 3.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define MAXN 1100010
#define bsize (1<<16)
using namespace std;
FILE* in = fopen("vsecvente.in", "r");
FILE* out = fopen("vsecvente.out", "w");
int Answer[MAXN];
int A[5];
int N, Q, Query, pos;
char s[bsize + 1];
void read (int &x){
    x=0;
    while( !isdigit(s[pos])){
        pos++;
        if(pos==bsize){
            fread(s, 1, bsize, in);
            pos=0;
        }
    }
    while( isdigit(s[pos])){
        x = x*10 + s[pos]-'0';
        pos++;
        if(pos==bsize){
            fread(s, 1, bsize, in);
            pos=0;
        }
    }
}
int main()
{
    pos=0;
    fread(s, 1, bsize, in);
	read(N);
	read(A[0]);
//	assert(A[0]<=550000 && A[0]>0);
	A[2] = INT_MAX; // A[-1] = INF
	for (int i = 0; i < N; ++i) {
		if (i == N - 1)
			A[(i + 1) % 3] = INT_MAX;
		else {
			read( A[(i + 1) % 3]);
          ///  assert(A[(i + 1)%3]<=550000 && A[(i + 1)%3]>0);
		}
		++Answer[A[i % 3]];
		if (A[(i + 2) % 3] <= A[i % 3])
			--Answer[A[i % 3]];
		if (A[(i + 1) % 3] < A[i % 3])
			--Answer[A[i % 3]];
	}
	for (int i = 0; i < MAXN; ++i)
		Answer[i] += Answer[i - 1];
	read(Q);
	for (int i = 0; i < Q; ++i) {
		read(Query);
		fprintf(out, "%d\n", Answer[Query]);
	}
	return 0;
}
```

## Resurse

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