Cod sursa(job #1139321)

Utilizator omerOmer Cerrahoglu omer Data 11 martie 2014 00:06:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include<stdio.h>
using namespace std;
FILE *f,*g;
int k,begin,end;
int front(int a[])
    {
        return a[begin];
    }
void popfront(int a[])
    {
        if (begin<end) begin++;
    }
void push(int a[],int b)
    {
        a[end++]=b;

    }
void popback(int a[])
    {
        if (begin<end) end--;
    }
bool empty(int a[])
    {
        if (begin==end) return 1; else return 0;
    }
void add(int a[],int x[],int b)
    {

        while(!empty(a)&&x[a[end-1]]>x[b]) popback(a);
        push(a,b);
    }
int betteradd(int a[],int x[],int b)
    {
        int q=a[begin];
        if (q==b-k) popfront(a);
        add(a,x,b);
        return q;
    }



int mini[500001];
int val[500001],n,i;
int main()
{

    int minim=-100000000,init=0,s;
    f=fopen("secventa.in","r");
    g=fopen("secventa.out","w");
    fscanf(f,"%d%d",&n,&k);
    for(i=1;i<=n;i++) fscanf(f,"%d",&val[i]);
    for(i=1;i<=k;i++) add(mini,val,i);
    for(i=k+1;i<=n;i++)
        {
          s=betteradd(mini,val,i);
          if (minim<val[s]) {minim=val[s];init=i-k;}
        }
    if (minim<val[mini[begin]]) {minim=val[mini[begin]];init=n-k+1;}
    fprintf(g,"%d %d %d",init,init+k-1,minim);
















    return 0;
}