Cod sursa(job #1803727)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 11 noiembrie 2016 18:58:50
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define nmx 500005
#include <limits.h>

using namespace std;
FILE *f=fopen("secventa.in","r");
FILE *f1=fopen("secventa.out","w");
int v[nmx],n,k,x;
long long s=0;
deque <int> q;
int maxi;
void citire( )
{
    fscanf(f,"%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);

}
void baza(int i)
{
    int b;
    b=q.front();
    if(v[b]>maxi)
    {
       maxi=v[b];
       x=i-k+1;

    }
}
void add(int i)
{
   while(!q.empty()&&v[q.back()]>v[i])
         q.pop_back();
    q.push_back(i);
}

void init()
{
    for(int i=1;i<=k;i++)
       add(i);
    x=1;
    maxi=v[q.front()];
}
void eraser(int i)
{
    while(!q.empty()&&(i-q.front()+1>k))
          q.pop_front();
}


void rezolvare( )
{
    init( );
    for(int i=k+1;i<=n;i++)
    {
        add(i);
        eraser(i);
        baza(i);
    }
}
int main()
{
    citire( );
    rezolvare();
    fprintf(f1,"%d %d %d",x,x+k-1,maxi);

    return 0;
}