Cod sursa(job #2999637)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 11 martie 2023 11:20:19
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 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 = -300001;
int start, stop;
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)
			{
				start = q[pq];
				stop = i;
				baza = a[q[pq]];
			}
	}
	cout << start << ' ' << stop << ' ' << baza;
	return 0;
}