Pagini recente » Cod sursa (job #1452888) | Cod sursa (job #1316081) | Cod sursa (job #884861) | Cod sursa (job #1186535) | Cod sursa (job #2498887)
#include <iostream>
#include <fstream>
#define MaxN 500001
using namespace std;
int q[MaxN],Left=0,Right=-1,n,k;
int sir[MaxN];
void push(int i)
{
int st=Left,m;
q[++Right]=i;
while(st<Right)
{
m=(st+Right)/2;
if(sir[i]<=sir[q[m]])
Right=m;
else
st=m+1;
}
q[st]=i;
}
void read()
{
char s[3000000];
ifstream f("secventa.in");
f>>n>>k;
f.get();
f.getline(s,3000000);
int i=1;
int semn=1;
int number=0;
for(char* p=s; *p!= NULL; p++)
{
if(*p == '-')
semn=-1;
else if('0'<= *p && *p <='9')
number=number*10+*p-'0';
else
{
sir[i++]=number*semn;
number=0;
semn=1;
}
}
f.close();
}
int main()
{
ofstream g("secventa.out");
read();
for(int i=1; i<=k; i++)
{
int st=Left,m;
q[++Right]=i;
while(st<Right)
{
m=(st+Right)/2;
if(sir[i]<=sir[q[m]])
Right=m;
else
st=m+1;
}
q[st]=i;
}
int st,dr,rez;
dr=k;
rez=sir[q[Left]];
for(int i=k+1; i<=n; i++)
{
if(q[Left]<=i-k)
Left++;
int st=Left,m;
q[++Right]=i;
while(st<Right)
{
m=(st+Right)/2;
if(sir[i]<=sir[q[m]])
Right=m;
else
st=m+1;
}
q[st]=i;
if(sir[q[Left]]>rez)
{
dr=i;
rez=sir[q[Left]];
}
}
st=dr-k+1;
sir[0]=-30001;
while(rez <= sir[--st]);
g<<st+1<<' '<<dr<<' '<<rez;
g.close();
return 0;
}