Cod sursa(job #1223823)
Utilizator | Data | 28 august 2014 22:23:29 | |
---|---|---|---|
Problema | Secventa | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.12 kb |
#include <cstdio>
using namespace std;
int n,k,a[500005],lista[500005][2],st,dr,inceput,sfirsit,baza;
char c;
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d %d\n",&n,&k);
c=' ';
int i=0,semn=1;
while (c!=EOF && c!='\n')
{
if (c==' ')
a[i]*=semn,semn=1,++i;
else
{
if (c=='-')
semn=-1;
else
{
a[i]=a[i]*10+(int)(c-'0');
}
}
c=getchar();
}
a[n]*=semn;
st=1; dr=1;
lista[1][0]=40000;
lista[1][1]=0;
for (int i=1;i<=k;++i)
{
++dr;
while (dr>st && lista[dr-1][0]>a[i]) --dr;
lista[dr][0]=a[i];
lista[dr][1]=i;
}
baza=lista[st][0];
inceput=1;
sfirsit=k;
for (int i=k+1;i<=n;++i)
{
if (i-lista[st][1]==k)
++st;
++dr;
while (dr>st && lista[dr-1][0]>a[i])
--dr;
lista[dr][0]=a[i];
lista[dr][1]=i;
if (lista[st][0]>baza)
{
baza=lista[st][0];
inceput=i-k+1;
sfirsit=i;
}
}
printf("%d %d %d",inceput,sfirsit,baza);
fclose(stdin);
fclose(stdout);
return 0;
}