Cod sursa(job #1803737)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 11 noiembrie 2016 19:14:37
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>
#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;

deque <int> q;
int maxi;
char s[3500000];
void citire( )
{
    fscanf(f,"%d%d\n",&n,&k);

    fgets(s,3500000,f);

    int k = 1;
    int p = 1;
    int l=strlen(s)-1;
    for(int i=0;i<strlen(s)-1;i++)
    {
        if(s[i]==' ')
        {
            v[k]*=p;
            k++;
            p=1;
        }
        else if(s[i]=='-')
        {
            p=-1;
        }
        else
        {
            v[k]=v[k]*10+(s[i]-'0');
        }
    }

}
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;
}