Cod sursa(job #1334938)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 4 februarie 2015 19:58:26
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <deque>
#include <bitset>
#include <complex>
#include <functional>
#include <memory>
#include <numeric>
#define x first
#define y second
typedef std::pair<int, int> pii;

using namespace std;

int n, x[500032], y[500032], k;
int front = 1, back = 0, MAX = -1<<30, cx, cy;
int main () {
	ifstream fin("secventa.in");
	ofstream fout("secventa.out");
	fin >> n >> k;
	for(int i = 0; i < n; i++)
		fin >> x[i];
	for(int i = 0; i < n; i++)
	{
		while(front <= back && x[i] <= x[y[back]])
			back--;
		back++;
		y[back] = i;
		if(y[front] == i - k)
			front++;
		if(i >= k - 1)
		{
			if(x[y[front]] > MAX)
			{	
				cx = i;
				MAX = x[y[front]];
			}
		}
	}
	cx++;
	cy = cx - k + 1;
	fout << cy << " " << cx << " " << MAX;
	return 0;
}