Cod sursa(job #331421)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 13 iulie 2009 21:53:52
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct qstack{
  int ni,nf;
  int val[500001];
  int poz[500001];
}qstack;

/*typedef struct qstack{
  int ni,nf;
  int *val;
  int *poz;
}qstack;*/

int n,k;
qstack s;

/*void pop(int poz){
  if(poz-s.v[s.ni].poz==k)
    s.ni++;
}

void push(int val, int poz){
  while(val<s.v[s.nf].val){
    s.nf--;
    if(s.nf<s.ni)
      break;
  }
  s.nf++;
  s.v[s.nf].val=val;
  s.v[s.nf].poz=poz;
}*/

int main(){
  int i,x,poz,a;
  /*freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);*/
  FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
  fscanf(f,"%d%d",&n,&k);
  fscanf(f,"%d",&a);
  s.val[s.ni=s.nf=1]=a;
  s.poz[s.nf]=1;
  for(i=2;i<=k;i++){
    fscanf(f,"%d",&a);
    //push(a,i);
    while(a<s.val[s.nf]){
      s.nf--;
      if(s.nf<s.ni)
        break;
    }
    s.nf++;
    s.val[s.nf]=a;
    s.poz[s.nf]=i;
  }
  int max=s.val[s.ni];
  poz=k;
  for(;i<=n;i++){
    fscanf(f,"%d",&a);
    //pop(i);
    if(i-s.poz[s.ni]==k)
      s.ni++;
    //push(a,i);
    while(a<s.val[s.nf]){
      s.nf--;
      if(s.nf<s.ni)
        break;
    }
    s.nf++;
    s.val[s.nf]=a;
    s.poz[s.nf]=i;
    if((x=s.val[s.ni])>max){
      max=x;
      poz=i;
    }
  }
  fprintf(g,"%d %d %d",poz-k+1,poz,max);
  return 0;
}