Cod sursa(job #2999624)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 11 martie 2023 11:13:41
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <climits>
using namespace std;

ifstream cin("secventa.in");
ofstream cout("secventa.out");

int pq = 0, uq = -1;

//pq - primul din coada
//uq - ultimul din coada

//In practica in coada NU retinem si valoarea elementului, ci doar indicele ( pt. ca avand indicele, elementul il luam direct din vector)

int n, k;
int a[500005];
int q[500005];
int baza = INT_MIN;
int start;
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		//actualizam coada luandu-l in calcul pe a[i]
		//deci golesc coada de elemntele mai mari deact a[i]
		while (pq <=uq && a[i] <= a[q[uq]])
			uq--;
		q[++uq] = i;
		//verific daca primul din coada mai face parte din secventa curenta. Daca nu, il sterg.
		if (q[pq] <= i - k)
			pq++;
		//afisez minimul
		if (i >= k)
			if (a[q[pq]] > baza)
			{
				baza = a[q[pq]];
				start = q[pq];
			}
	}
	cout << start << ' ' << start + k - 1 << ' ' << baza;
	return 0;
}