Cod sursa(job #211694)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 3 octombrie 2008 13:23:55
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <deque>
#include <stdio.h>
#define MAX 5000000

using namespace std;

deque <int> coada;

int sir[MAX/10],n,k;
int start,max_min;

void citire()
{
    scanf ("%d %d",&n,&k);
    char ca[MAX],c;
    int j;
    int semn;
    scanf ("%c",&c);
    fgets(ca,MAX,stdin);
    for (int i=0;i<n;i++)
    {
        semn=0;
        sir[i]=0;
        while(ca[j]!='-' && (ca[j]<'0' || ca[j]>'9'))
             j++;
        if(ca[j]=='-')
          {
           semn=1;
           j++;
          }
        while(ca[j]>='0' && ca[j]<='9')
             {
              sir[i]=sir[i]*10+(ca[j]-'0');
              j++;
             }
        if(semn)
          sir[i]=-sir[i];
    }
}

void solve()
{
    start=0;
    for (int i=0;i<k;i++)
    {
        while (!coada.empty() && sir[coada.back()]>=sir[i])
            coada.pop_back();
        coada.push_back(i);
    }

    max_min=sir[coada.front()];

    for (int i=k;i<n;i++)
    {
        if (coada.front()==i-k)
            coada.pop_front();
        while(!coada.empty() && sir[coada.back()]>=sir[i])
            coada.pop_back();
        coada.push_back(i);
        if (sir[coada.front()]>max_min)
        {
                max_min=sir[coada.front()];
                start=i-k+1;
        }
    }
}

void afisare()
{
    //fout<<start+1<<" "<<start+k<<" "<<max_min<<"\n";
    printf("%d %d %d\n",start+1,start+k,max_min);
}

int main ()
{

freopen ("secventa.in","r",stdin);
freopen ("secventa.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}