Cod sursa(job #96939)

Utilizator gigi_becaliGigi Becali gigi_becali Data 4 noiembrie 2007 10:53:00
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <string>
#define maxn 500001

short a[maxn];
int dq[maxn][2];
int first, last;
int n, K;

void read()
{
  freopen("secventa.in","r",stdin);
  scanf("%d %d\n", &n, &K);
  for(int i=1;i<=n;++i) scanf("%d ", a+i);
}

inline void insert(int v, int poz)
{
  while(first<=last && dq[last][0]>v) --last;
  ++last;
  dq[last][0]=v;
  dq[last][1]=poz;
}

inline short query(int a, int b)
{
  while(first<=last && dq[first][1]<a) ++first;
  return dq[first][0];
}

void solve()
{
  int i, p, q, sol=-0x3f3f3f3f;
  for(i=1;i<K;++i) insert(a[i], i);

  for(i=K;i<=n;++i)
    {
      insert(a[i], i);
      int t=query(i-K+1, i);
      if(t>sol)
	{
	  sol=t;
	  p=i-K+1;
	  q=i;
	}
    }

  printf("%d %d %d\n", p, q, sol);


}

int main()
{

  freopen("secventa.out","w",stdout);
  read();
  solve();
  return 0;
}