Cod sursa(job #461939)

Utilizator S7012MYPetru Trimbitas S7012MY Data 9 iunie 2010 11:58:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
using namespace std;

template <class T>
class coada {
public:
	T val;
	void adauga(T deadaugat) { val=deadaugat; }
};

coada<int> c[500001];

int main()
{
	int k,n,i,v1,v2,inc,sfc,init[500001],sol=-99999999;
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f>>n>>k;
	v1=v2=inc=sfc=1;
	c[inc].adauga(1);
	for(i=1; i<=n; i++) f>>init[i];
	for(i=2; i<=n; i++) {
		for( ; inc<=sfc && init[i]<=init[c[sfc].val]; sfc--);
		c[++sfc].adauga(i);
		if(i>=k && init[c[inc].val]>sol){
			v1=i-k+1; 
			v2=i;
			sol=init[c[inc].val];
		}
		if(c[inc].val<=i-k+1)
            ++inc;
	}
	g<<v1<<" "<<v2<<" "<<sol<<"\n";
	f.close();
	g.close();
	return 0;
}