Pagini recente » Cod sursa (job #130047) | Cod sursa (job #1490385) | Cod sursa (job #282943) | Cod sursa (job #1732051) | Cod sursa (job #119918)
Cod sursa(job #119918)
#include<stdio.h>
#include<iostream>
using namespace std;
int n,k,a[500001],co[500001],min,minmax;
char au[1000002];
int cauta(int p,int u,int x)
{
int m;
while(p<u){
m=(p+u)/2;
if(x<=a[co[m]])
u=m;
else
p=m+1;
}
if(a[co[p]]<x)
return p+1;
return p;
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int min=30001,max,p=0,u=0,aa,bb;
scanf("%d%d\n",&n,&k);
int r,t=1;
int i;
while(scanf("%c",&au[t])!=EOF)
++t;
--t;
char semn='1';
for(r=1; au[r]!=' '; ++r)
{
if(au[r]!='-'){
a[1]+=a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1];
a[1]+=int(au[r])-48;}
else
semn='0';
}
if(semn=='0')
a[1]*=-1;
char ok;
co[u++]=1;
for(i=2; i<=k; i++){
semn='1';++r;
for(r; r<t&&au[r]!=' '; ++r)
{
if(au[i]!='-'){
a[i]+=a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i];
a[i]+=int(au[r])-48;}
else
semn='0';
}
if(semn=='0')
a[i]*=(-1);
u=cauta(p,u-1,a[i]);
co[u++]=i;
if(a[co[p]]<min)
min=a[co[p]];
}
max=min;
aa=1;bb=k;
for(i=k+1; i<=n; i++)
{ semn='1'; ++r;
for(r; r<t&&au[r]!=' '; ++r)
{
if(au[i]!='-'){
a[i]+=a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i];
a[i]+=int(au[r])-48;}
else
semn='0';
}
if(semn=='0')
a[i]*=(-1);
if(co[p]+k<=i)
++p;
u=cauta(p,u-1,a[i]);
co[u++]=i;
min=a[co[p]];
if(min>max){
max=min;
aa=i-k+1;
bb=i;
}
}
printf("%d %d %d\n",aa,bb,max);
return 0;
}