Cod sursa(job #67023)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 22 iunie 2007 11:29:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
//(c) @author Mircea Dima
#include <cstdio>
#include <string>
#include <cstdlib>
#define MAXN 500001
#define oo 0x3f3f3f3f
using namespace std;

int deque[MAXN][2];
short A[MAXN];
char aux[8*MAXN];
int N, L, r,P, S,capat, coada, MAX;
 
void citire()
// citim cu gets, fgets, sau fread(cel din urma pt citirea fisierului k intreg)
// deoarece sunt multe elemente d citit, scanf-ul ar fi "mancat" aproape tot timpul
// citirea cu scanf pt n=500000 ar fi durat km 0,16 p cand 
// citirea cu gets sau read  dureaza 0,007 :D 
{
  int i;

  freopen("secventa.in", "r", stdin);  
  scanf("%d %d\n", &N, &L);
  fgets(aux, 7*N, stdin);   
  // se poate shi asha:             gets(aux)          
  // sau asha:                      fread(aux, sizeof(char), 7*N, stdin);
  // fread citeshte tot fisierul d la pointerul indicat ( in cazul d fatza stdin)
  // dak vrei sa foloseshti FILE*f=fopen=("secventa.in", "r"); vei folosi in loc d stdin pointerul "f" ;)
  //gets nu merge cu FILE*....
char *p;
  p=strtok(aux, " ");

 for(i=1;i<=N;i++)
   {
     A[i]=atoi(p);
     p=strtok(NULL, " ");
   }

}

void insert(int value, int pos)
{
	while(capat<=coada && value<deque[coada][0]) --coada;
	deque[++coada][0]=value;
	deque[coada][1]=pos;
}

int query()
{
	while(capat<=coada && deque[capat][1]<P) ++capat;
	return deque[capat][0];
}


void calcul()
{
   int i, r;
   capat=1, coada=0, S=0, MAX=-oo;
  
  for(i=1 ; i<L ; i++)  insert(A[i], i);

  for(i=L , P=1 ; i<=N ; ++i , ++P )
    {
	  insert(A[i], i);
	  r=query();
      if(r>MAX) MAX=r, S=i;
    }

  int poz=S-L+1;

  freopen("secventa.out", "w", stdout);
  printf("%d %d %d\n", poz, S, MAX);

 }

int main()
{
  citire();
  calcul();
  return 0;
}