Cod sursa(job #2722927)

Utilizator DragosC1Dragos DragosC1 Data 13 martie 2021 13:14:58
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <deque>
using namespace std;

int n, k;
int a[500001];
int Max, st, dr;
void read() {
	int i;
	ifstream f("secventa.in");
	f >> n >> k;
	for (i = 1; i <= n; i++) 
		f >> a[i];
	f.close();
}

deque<int> dq;

void solve() {
	int i;
	Max = 0;
	for (i = 1; i <= n; i++) {
		while (dq.size() > 0 && a[i] <= a[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		if (dq.front() <= i - k)
			dq.pop_front();
		if (i >= k)
			if (a[dq.front()] > Max) {
				Max = a[dq.front()];
				st = dq.front(), dr = i;
			}
	}
}

void output() {
	ofstream g("secventa.out");
	g << st << ' ' << dr << ' ' <<  Max;
	g.close();
}

int main() {
	read();
	solve();
	output();
	return 0;
}