Pagini recente » Cod sursa (job #1194344) | Cod sursa (job #808321) | Cod sursa (job #3304244) | Cod sursa (job #1309967) | Cod sursa (job #807503)
Cod sursa(job #807503)
#include<stdio.h>
#include<string.h>
#define Nmax 500001
int V[Nmax], Deque[Nmax], N, k, st, dr, poz, minim;
char buff[Nmax*15];
int main() {
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int i, nr, dim;
char minus;
scanf("%d %d\n",&N,&k);
fgets(buff,Nmax*15,stdin);
dim = strlen(buff);
i = 0;
nr = 0;
minus = 0;
while(i<dim) {
if(buff[i] == '-') {
minus = 1;
++i;
continue;
}
if(buff[i]>='0' && buff[i]<='9') {
while(buff[i]>='0' && buff[i]<='9' && i<dim) {
nr = nr*10 + buff[i]-'0';
++i;
}
if(minus) {
nr = -nr;
minus = 0;
}
V[++V[0]] = nr;
nr = 0;
continue;
}
if(buff[i]==' ') {
++i;
continue;
}
}
st = dr = 1;
Deque[st] = 1;
minim = -1<<30;
for(i=2; i<=N; i++) {
while(V[i] <= V[Deque[dr]] && st<=dr)
dr--;
// sterg din deque toate elem mai mari ca V[i] formand mereu in felul asta un sir crescator in deque
Deque[++dr] = i;
// adaug pozitia elementului curent
while(Deque[st]+k <= i)
st++;
if(minim < V[Deque[st]] && i>=k) {
minim = V[Deque[st]];
poz = i;
}
}
printf("%d %d %d\n",poz-k+1,poz,minim);
return 0;
}