Cod sursa(job #66996)

Utilizator gigi_becaliGigi Becali gigi_becali Data 22 iunie 2007 00:51:54
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
//(c) @author Mircea Dima
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#define MAXN 500001
#define oo 0x3f3f3f3f
using namespace std;


short A[MAXN];
char aux[8*MAXN];
int N, L, r,P, S,capat, coada, MAX;
 
struct nod { short val;int poz;nod(){}; nod(short a, int b){val=a; poz=b;};};

bool operator <(const nod &a, const nod &b)
{
	if(a.val<b.val) return 1;
	if(a.val==b.val && a.poz<b.poz) return 1;
	return 0;
}


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 calcul()
{
   int i, r;
   capat=1, coada=0, S=0, MAX=-oo;
	set<nod>Q;
  for(i=1 ; i<L ; i++) Q.insert(nod(A[i], i));
  
  for(i=L ; i<=N ; ++i )
    {
		Q.insert(nod(A[i],i));
		r=Q.begin()->val;
		if(r>MAX) MAX=r, S=i;
		Q.erase(nod(A[i-L+1], i-L+1));
    }

  int poz=S-L+1;

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

 }

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