Cod sursa(job #1509634)

Utilizator tudi98Cozma Tudor tudi98 Data 24 octombrie 2015 10:02:52
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <deque>
using namespace std;
 
int a[500001];
deque<int> D;
string s;
int pos = 0;

int nextInt()
{
	while (s[pos] == ' ' && pos < s.size()) ++pos;
	   
	int Ret = 0;
	int sgn = 1;
	if (s[pos] == '-') sgn = -1, ++pos;
	while (s.size() > pos && s[pos] != ' ')
	{
		Ret * 10;
		Ret += s[pos] - '0';
		++pos;
	}

	return Ret * sgn;
}
 
int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
 
    int N,K;
 
    fin >> N >> K;

    fin.get();
    getline(fin,s);

    for (int i = 1; i <= N; i++)   
       	a[i] = nextInt();    

    int best = -30001,from = 0;
 
    for (int i = 1; i <= N; i++)
    {
        while (!D.empty() && i - D.front() + 1 > K)
            D.pop_front();
        while (!D.empty() && a[D.back()] > a[i])
            D.pop_back();
 
        D.push_back(i);
 
        if (i >= K && a[D.front()] > best)
        {
            best = a[D.front()];
            from = i;
        }
    }
 
    fout << from - K + 1 << " " << from << " " << best;
}