Cod sursa(job #789920)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 septembrie 2012 21:49:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int a[500001],k,n;
deque<int>q;
int main()
{
    int i,max=-31001,y;
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>a[i];
    for (i=1;i<=n;i++)
    {
        while (!q.empty() && a[q.back()]>=a[i])
        {
            q.pop_back();
        }
        q.push_back(i);
        if (q.front()==i-k)
        {
            q.pop_front();
        }
        if (i >= k && a[q.front()] > max)
            {
                max=a[q.front()];
                y=i;
            }
    }
    fout<<y-k+1<<" "<<y<<" "<<max<<"\n";
    return 0;
}