Cod sursa(job #97624)

Utilizator gigi_becaliGigi Becali gigi_becali Data 7 noiembrie 2007 19:21:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <fstream.h>
#include <string>
#define maxn 500001

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

void read()
{
  ifstream f("secventa.in");
  f>>n>>K;
  
  for(int i=1;i<=n;++i)f>>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;
	}
    }

  ofstream g("secventa.out");
  g<<p<<" "<<q<<" "<<sol<<"\n";
 


}

int main()
{

  
  read();
  solve();
  return 0;
}