Pagini recente » Cod sursa (job #444827) | Cod sursa (job #2114544) | Cod sursa (job #2044066) | Istoria paginii runda/riad2 | Cod sursa (job #188192)
Cod sursa(job #188192)
#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,MAX_N,stdin);
int ind=0,x=1,p=1;
int len=strlen(s+1);
while (p<=len){
if (s[p]=='-'){x=-1;++p;} else
if (s[p]==' '){++ind;v[ind]=x;x=1;++p;} else
if (s[p]>='0' && s[p]<'9'){
x*=(s[p]-'0');++p;
} else {++p;}
}
if (x!=1){++ind;v[ind]=x;}
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;
}