Cod sursa(job #96940)

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

short a[maxn];
int dq[maxn][2];
int first, last;
int n, K;
char ax[500000*7];
void read()
{
  freopen("secventa.in","r",stdin);
  scanf("%d %d\n", &n, &K);
  gets(ax);
  char *t;
  t=strtok(ax, " ");
  a[1]=atoi(t);
  
  for(int i=2;i<=n;++i)
    {
      t=strtok(0," ");
      a[i]=atoi(t);
    }
  // 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;
}