Cod sursa(job #789853)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 septembrie 2012 17:41:29
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<iostream>
#include<queue>
#include<fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n, k, i, a[500001], res, st, dr;
deque<int>dq;
int main()
{
    fin >> n >> k;
    for ( i = 1; i <= n; i++ )
    {
        fin >> a[i];
    }
    for ( i = 1; i <= n; i++ )
    {
        while ( !dq.empty() && a[i] < a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if ( i >= k )
        {
            if ( !dq.empty() && dq.front() <= i-k )
            {
                dq.pop_front();
            }
            if ( res < a[dq.front()])
            {
                res = a[dq.front()];
                st = i-k+1;
                dr = i;
            }
        }
    }
    fout << st << ' ' << dr << ' ' << res;
    fin.close();
    fout.close();
    return 0;
}