Cod sursa(job #2314526)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 8 ianuarie 2019 17:32:06
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ofstream out("secventa.out");

	
class InParser {
	
private:
	
	FILE *fin;
	char *buff;
	int sp;
	
	char read_ch() 
	{
		sp++;
	
		if(sp == 4096) 
		{
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
	
		return buff[sp];
	}

public:
	
	InParser(const char* nume) 
	{
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) 
	{
		char c;
		while(!isdigit(c = read_ch()) && c != '-');
	
		int sgn = 1;
	
		if(c == '-') 
		{
			n = 0;
			sgn = -1;
		} 
		else 
			n = c - '0';
	
		while(isdigit(c = read_ch())) 
			n = 10 * n + c - '0';
			
		n *= sgn;
	
		return *this;
	}
};

const int DIM = 5e5 + 7;

deque <int> d;
int v[DIM];

int main()
{
	InParser fin("secventa.in");
	
	int n, k;
	fin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		fin >> v[i];
	
	int mx = -1e9;
	int r = k;
	
	for(int i = 1; i <= n; i++)
	{
		while(!d.empty() && v[d.back()] >= v[i])
			d.pop_back();
		
		d.push_back(i);
		
		if(i - d.front() == k)
			d.pop_front();
		
		if(i >= k && v[d.front()] > mx)
		{
			mx = v[d.front()];
			r = i;
		}
	}
	
	out << r - k + 1 << ' ' << r << ' ' << mx;
}