Cod sursa(job #114102)

Utilizator scvalexAlexandru Scvortov scvalex Data 12 decembrie 2007 17:52:50
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

int N(0),
	K(0);

short a[500001],
	  dpoz[50001],
	  dval[50001];
int beg(0),
	end(0);

void print_deque() {
	for (int i = beg; i < end; ++i)
		cout << dpoz[i] << "\t";
	cout << endl;
	for (int i = beg; i < end; ++i)
		cout << dval[i] << "\t";
	cout << endl << endl;
}

int main(int argc, char *argv[]) {
	ifstream fin("secventa.in");
	fin >> N >> K;
	for (int i(0); i < N; ++i)
		fin >> a[i];
	fin.close();

	int maxi(0),
		max(-666);

	int i(0);
	for (; i < K; ++i) {
		while ((beg < end) && (dpoz[beg] <= i - K))
			++beg;
		while ((end > beg) && (dval[end - 1] >= a[i]))
			--end;
		dval[end] = a[i];
		dpoz[end++] = i;
	}

	if ((max < dval[beg]) || (max == -666)) {
		max = dval[beg];
		maxi = dpoz[beg] - (K - (dpoz[end - 1] - dpoz[beg] + 1));
	}

//	print_deque();

	for (; i < N; ++i) {
		while ((beg < end) && (dpoz[beg] <= i - K))
			++beg;
		while ((end > beg) && (dval[end - 1] >= a[i]))
			--end;
		dval[end] = a[i];
		dpoz[end++] = i;
		if ((max < dval[beg]) || (max == -666)) {
			max = dval[beg];
			maxi = dpoz[beg] - (K - (dpoz[end - 1] - dpoz[beg] + 1));
		}
//		print_deque();
	}

	ofstream fout("secventa.out");
	fout << maxi + 1 << " " << maxi + K << " " << max << endl;
	fout.close();

	return 0;
}