Cod sursa(job #331202)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 12 iulie 2009 23:44:33
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>

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

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

int n,k,a[500001];
qstack s;

/*void pop(int poz){
  if(s.v[s.ni].poz-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;
  freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);
  scanf("%d%d",&n,&k);
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
  s.v[s.ni=s.nf=1].val=a[n];
  s.v[s.nf].poz=n;
  for(i=n-1;i>n-k;i--)    
    push(a[i],i);
  int max=s.v[s.ni].val;
  poz=n-k+1;
  for(;i>=1;i--){
    if(s.v[s.ni].poz-i==k)
      s.ni++;
    while(a[i]<=s.v[s.nf].val){
      s.nf--;
      if(s.nf<s.ni)
        break;
    }
    s.nf++;
    s.v[s.nf].val=a[i];
    s.v[s.nf].poz=i;
    if((x=s.v[s.ni].val)>=max){
      max=x;
      poz=i;
    }
  }
  printf("%d %d %d",poz,poz+k-1,max);
  return 0;
}