Cod sursa(job #331751)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 15 iulie 2009 10:35:54
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>

typedef struct val{
  int val,poz;
}val;

typedef struct qstack{
  int ni,nf;
  val v[500001];
}qstack;

int n,k;
qstack s;
char sir[3500001];

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 next_number(int *j){
  int nr=0,minus=0;
  if(sir[*j]=='-'){
    minus=1;
    (*j)++;
  }
  while(sir[*j]!=' '){
    nr=nr*10+sir[*j]-'0';
    (*j)++;
  }
  (*j)++;
  if(!minus)
    return nr;
  return -nr;
}
     

int main(){
  int i,x,poz,a,j=0;
  freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);
  scanf("%d%d\n",&n,&k);
  fgets(sir,3500000,stdin);
  sir[strlen(sir)-1]=' ';
  a=next_number(&j);
  s.v[s.ni=s.nf=1].val=a;
  s.v[s.nf].poz=1;
  for(i=2;i<=k;i++){
    a=next_number(&j);
    push(a,i);
  }
  int max=s.v[s.ni].val;
  poz=k;
  for(;i<=n;i++){
    a=next_number(&j);
    pop(i);
    push(a,i);
    if((x=s.v[s.ni].val)>max){
      max=x;
      poz=i;
    }
  }
  printf("%d %d %d",poz-k+1,poz,max);
  return 0;
}