Pagini recente » Cod sursa (job #469632) | Cod sursa (job #888995) | Cod sursa (job #3130030) | Cod sursa (job #371796) | Cod sursa (job #188235)
Cod sursa(job #188235)
#include <iostream>
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define INF 2000000000
#define MAX_N 500010
using namespace std;
int v[MAX_N],n,k;
struct el {
int vl,deadline;
} deq[MAX_N];
char s[7000000];
void iofile(void){
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);
scanf("%d %d\n",&n,&k);
fgets(s+1,7000000,stdin);
int len=strlen(s+1)-1;
int i=1;
int ind=0,p=1,x=0;
while (i<=len){
p=1;
x=0;
if (s[i]=='-'){p=-1;++i;}
for (;s[i]!=' ' && i<=len;++i){
x*=10;x+=s[i]-'0';
}
++ind;
v[ind]=x*p;
++i;
}
fclose(stdin);
}
void solve(void){
int pin,maxim=-INF,time=1;
int st=1,dr=1;
deq[1].vl=v[1];
deq[1].deadline=1+k;
for (int i=2;i<=n;++i){
++time;
while (st<=dr && deq[st].deadline<=time){++st;}
while (dr>=st && deq[dr].vl>v[i]){--dr;}
++dr;
deq[dr].vl=v[i];
deq[dr].deadline=i+k;
if (i>=k && deq[st].vl>maxim){maxim=deq[st].vl;pin=deq[dr].deadline-k-k+1;}
}
int pend=pin+k-1;
while (pin>1 && v[pin-1]>=maxim){--pin;}
printf("%d %d %d\n",pin,pend,maxim);
fclose(stdout);
return;
}
int main(void){
iofile();
solve();
return 0;
}