Cod sursa(job #1309408)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 5 ianuarie 2015 18:52:03
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

int q[500005], p[500005], n, k;

int main()
{
	int st, dr, baza, i, x, poz;
	ifstream fin("secventa.in");
	ofstream fout("secventa.out");
	fin >> n >> k;
	// primele k numere

	st = 0;
     dr = -1;
	for (i = 1; i <= k; i++)
	{
		fin >> x;
		while (st <= dr && q[dr] >= x) dr--;
		q[++dr] = x;
		p[dr] = i;
	}
	baza = q[st];
	poz = 1;
	// citim restul numerelor
	for (i = k + 1; i <= n; i++)
	{
		fin >> x;
		while (st <= dr && q[dr] >= x) dr--;
		q[++dr] = x;
		p[dr] = i;
		if (p[st] <= i-k) st++;
		if (baza < q[st])
		{
			baza = q[st];
			poz = p[st];
}
	}

    fout << poz << " " << (poz + k - 1) << " " << baza << "\n";
    fin.close();
    fout.close();
    return 0;
}