Cod sursa(job #1755782)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 11 septembrie 2016 01:03:53
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

#define pp pair<int, int>
#define x first
#define y second

const int NMAX = 5e5 + 5;

int n; int k; int b = -0x3f3f3f3f;
int a[NMAX];
int st, dr;
deque<pp> q;

int main() {

	fin >> n >> k;

	for(int i = 1; i <= n; ++i)
		fin >> a[i];

	//j1 < j2 , a[j1] > a[j2], j1 poate fi eliminat

	for(int i = 1; i <= k - 1; ++i) {

		while(q.empty() == false && q.back().first >= a[i])
			q.pop_back();

		q.push_back({a[i], i});
	}

	for(int i = k; i <= n ; ++i) {

		while(q.empty() == false && q.back().first >= a[i])
			q.pop_back();

		q.push_back({a[i], i});

		if(q.empty() == false && i - q.front().second + 1 > k) 
			q.pop_front();

		if(q.front().first > b) {
			b = q.front().first;
			st = i - k + 1;
			dr = i;
		}
	}

	fout << st << ' ' << dr << ' ' << b  << '\n';

	return 0;
}