Cod sursa(job #770166)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 22 iulie 2012 12:55:43
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream>

using namespace std;

#define MAXN 500002

int A[ MAXN ], v[ MAXN ], n, k, x, y, res = -MAXN;

void solve()
{
	ifstream f("secventa.in");
	
	int i, st = 1, end = 0;
	
	f >> n >> k;
	for(i = 1; i <= n; i++)
	{
		f >> v[i];
		
		while(v[i] <= v[ A[end] ] && st <= end)
			end--;
		end++, A[end] = i;
		
		if(i - k == A[st])
			st++;
		
		if(i >= k)
			if(v[ A[st] ] > res)
				res = v[ A[st] ], x = i - k + 1, y = i;
	}
	
	f.close();
	
}

void write()
{
	ofstream g("secventa.out");
	
	g << x << " " << y << " " << res << '\n'; 
	
	g.close();
}

int main()
{
	solve();
	write();
	return 0;
}