Cod sursa(job #1755789)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 11 septembrie 2016 01:12:07
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 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

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

int main() {

	std::ios::sync_with_stdio(false);

	fin >> n >> k;

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

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

		fin >> a;

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

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

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

		fin >> a;

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

		q.push_back({a, 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;
}