Cod sursa(job #1139463)

Utilizator omerOmer Cerrahoglu omer Data 11 martie 2014 10:38:16
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include<stdio.h>
#include<deque>
using namespace std;
FILE *f,*g;
deque<int> mini;
int val[500001],n,k,i;
void add(int a)
{
   while(!mini.empty()&&val[mini.back()]>val[a]) mini.pop_back();
   mini.push_back(a);
}
int uberadd(int a)
{
    int q=mini.front();
    add(a);
    if (q==a-k) mini.pop_front();
    return q;

}

int main()
{
    int q,minim=-31000,init;
    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]);
        if (i<=k) add(i);
        else {
            q=uberadd(i);
            if (val[q]>minim) {minim=val[q];init=i-k;}
        }
    }
    if (minim<val[mini.front()]) {minim=val[mini.front()];init=n-k+1;}
    fprintf(g,"%d %d %d",init,init+k-1,minim);








    return 0;
}