Pagini recente » Cod sursa (job #119914) | Cod sursa (job #1649110) | Cod sursa (job #1010679) | Cod sursa (job #1734876) | Cod sursa (job #88076)
Cod sursa(job #88076)
#include <cstdio>
using namespace std;
struct deque
{
int pos,val;
} q[500000];
int v[500000];
int n,k;
int d1,d2;
int last,first,baza;
void citire()
{
freopen("secventa.in","r",stdin);
/* scanf("%d%d",&n,&k);
for (int i=0;i<n;i++)
scanf("%d",&v[i]);
fclose(stdin);
*/
char sir[400000];
fgets(sir,10,stdin);
int i;
for(i=0; sir[i] != ' '; i++)
n=n*10 + sir[i]-'0';
i++;
for (;sir[i] !='\n';i++)
k=k*10 + sir[i]-'0';
// Gata n si k
fgets(sir,350000,stdin);
int j=0;
for (int i=0;i<n;i++)
{
if (sir[j]=='-')
{
v[i]=-1 * (sir[j+1] -'0');
j+=2;
}
else
v[i]=0;
while (('0'<=sir[j]) && (sir[j]<='9'))
{
v[i]=v[i]*10 + sir[j]-'0';
j++;
}
j++;
}
}
void calcul()
{
d1=0;
d2=0;
q[0].val=v[0];
q[0].pos=0;
for (int i=1;i<n;i++)
{
while (q[d1].pos<=i-k && d1<=d2)
d1++;
while (q[d2].val>=v[i] && d2>=d1)
d2--;
d2++;
q[d2].val=v[i];
q[d2].pos=i;
if (((q[d1].val > baza) && (i>k-1)) || (i==k-1))
{
baza=q[d1].val;
first=i-k+2;
last=i+1;
}
}
}
int main()
{
citire();
calcul();
freopen("secventa.out","w",stdout);
printf("%d %d %d",first,last,baza);
fclose(stdout);
return 0;
}