Cod sursa(job #1697406)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 1 mai 2016 22:19:15
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <cstdio>
#include <iostream>
#include <vector>
#include <deque>
#define NMAX 5000005
#define HMAX 100005
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> pii;

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

int main() {
	int n,k,i,val,valmax,st,dr;
	long long sum=0;

	fin>>n>>k;

	deque<pii> dq;
	valmax=-INF;
	for(i=1;i<=n;++i) {
		fin>>val;
		while(!dq.empty() && dq.back().second>val) dq.pop_back();

		dq.push_back({i,val});

		if(dq.front().first<=i-k) dq.pop_front();
		if(i>=k) {
			if(dq.front().second > valmax) {

				valmax=dq.front().second;
				cout<<valmax<<' ';
				st=i-k+1;
				dr=i;
			}
		}
	}

	fout<<st<<' '<<dr<<' '<<valmax;

	return 0;
}