Cod sursa(job #130065)

Utilizator FlorianFlorian Marcu Florian Data 31 ianuarie 2008 09:15:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<values.h>
#include<string.h>
FILE*f=fopen("secventa.in","r");
FILE*g=fopen("secventa.out","w");
int a[500003];

int n,k;
void read();
int main()
{
read();
int q[500004],rez,i,st,dr,poz;
rez=-MAXINT;
st=1;dr=0;
for (i=1;i<k;i++)
 {
 while(dr>=st&&a[i]<=a[q[dr]]) dr--;
 dr++;
 q[dr]=i;}
for (i=k;i<=n;i++)
	{
	while(st<=dr&&a[i]<=a[q[dr]]) dr--;
	dr++;
	q[dr]=i;
	while(st<=dr&&q[st]<i-k+1) st++;
	if (a[q[st]]>rez) {rez=a[q[st]]; poz=i;}}
fprintf(g,"%d %d %d",poz-k+1,poz,rez);
return 0;}

void read()
{
  fscanf(f,"%d %d",&n,&k);
  long semn=0, lung;
  char s[2000099];
  fgetc(f);
  fgets(s, 2000097,f);
  lung=strlen(s);
  int nr=1;
  for (int i=0; i<lung; i++)
    {
      if (s[i]=='-') semn=1;
      if (s[i]>='0' && s[i]<='9')
               {
          a[nr]=a[nr]*10+(s[i]-'0');
        }
      if (s[i]==' ' && semn==1)  a[nr]*=-1, semn=0;
      if(s[i]==' ') nr++;
    }
}