Cod sursa(job #1226554)

Utilizator harababurelPuscas Sergiu harababurel Data 6 septembrie 2014 04:00:41
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
#define nmax 500005
using namespace std;

int n, k, l, r, x=1, sol=-nmax, v[nmax];
bool neg[nmax];
deque <int> D;
string s;

int main() {
	ifstream f("secventa.in");
	ofstream g("secventa.out");

	f>>n>>k;
	f.get();
	getline(f, s);
	for(int i=0; i<int(s.size()); i++) {
		if('0' <= s[i] && s[i] <= '9') v[x] = v[x] * 10 + int(s[i]) - 48;
		if(s[i] == ' ') ++x;
		if(s[i] == '-') neg[x] = true;
	}

	for(int i=1; i<=n; i++) {
			if(neg[i]) v[i] *= -1;
			while(!D.empty() && v[D.back()] >= v[i]) D.pop_back();
			D.push_back(i);

			if(i >= k) {
				if(D.front() + k <= i) D.pop_front();
				if(v[D.front()] > sol) {
					sol = v[D.front()];
					r = i;
				}
			}
	}

	l = r;
	while(l>1 && v[l-1] >= sol) l--;

	g<<l<<" "<<r<<" "<<sol<<"\n";
	return 0;
}