Cod sursa(job #2351898)

Utilizator dorufDoru Floare doruf Data 22 februarie 2019 19:51:57
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <iostream>
#include <deque>
using namespace std;

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

void read();
void write();

deque<int>  Q; // un minQ cu pozitii

int a[500001];
int n, k;
int p, v;
int I, J, Max;

void Get(int &x);

int main()
{
	Get(n); Get(k);

	int i, val;
	for (i = 1; i <= n; ++i)
	{
		Get(a[i]);
        while (!Q.empty() && a[i] < a[Q.back()])
            Q.pop_back();

        Q.push_back(i);

        if (Q.back() - Q.front() + 1 > k)
            Q.pop_front();

        if (a[Q.front()] > Max)
        {
            Max = a[Q.front()];
            I = Q.front();
            J = Q.back();
        }
        else
            if (a[Q.front()] == Max && Q.back() < J)
            {
                J = Q.back();
                I = Q.front();
            }

	}

	fout << I << ' ' << J << ' ' << Max;


	return 0;
}

const int Lim = 1 << 20;
int p1 =  Lim - 1;
char s[Lim];

void Next()
{
    if (++p1 == Lim)
        fin.get(s, Lim + 1, EOF), p1 = 0;
}

void Get(int &x)
{
	while (s[p1] < '0' || s[p1] > '9')
	{
		if (s[p1] == '-')
			break;
		Next();
	}

	int sgn = 1;
	if (s[p1] == '-')
	{
		sgn = -1;
		Next();
	}

    for (x = 0; s[p1] >= '0' && s[p1] <= '9'; Next())
        x = x * 10 + s[p1] - '0';
    x *= sgn;
}