Cod sursa(job #114132)

Utilizator scvalexAlexandru Scvortov scvalex Data 12 decembrie 2007 19:11:06
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

int N(0),
	K(0);

int a[500001],
	  dpoz[500001],
	  dval[500001];
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];
	}

//	cout << max << " " << " " << a[maxi] << " " << a[maxi + 1] << " " << maxi << " " << i << endl;

//	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 ((beg > end) || (end > 500001))
			exit(113);

		if ((max < dval[beg]) || (max == -666)) {
			max = dval[beg];
			maxi = dpoz[beg];
			if (a[maxi] != max) {
				cout << i << endl;
				return 1;
			}
		}
//		print_deque();
	}

	int dif = K;
	for (int i = maxi; (dif > 0) && (a[i] >= max) && (i >= 0); --i)
		--dif;

//	cout << max << " " << " " << a[maxi] << " " << a[maxi + 1] << " " << maxi << " " << i << endl;
//	cout << dif << endl;

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

	return 0;
}