Pagini recente » Cod sursa (job #514228) | Cod sursa (job #2653839) | Cod sursa (job #20310) | Cod sursa (job #469173) | Cod sursa (job #807510)
Cod sursa(job #807510)
#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 get_number(int &ind, int dim) {
char minus = 0;
int nr = 0;
if(buff[ind] == '-') {
++ind;
minus = 1;
}
while(buff[ind]>='0' && buff[ind]<='9' && ind<dim) {
nr = nr*10 + buff[ind]-'0';
++ind;
}
++ind;
return !minus ? nr : -nr;
}
int main() {
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int i, ind, dim;
scanf("%d %d\n",&N,&k);
dr = 0;
st = 1;
minim = -1<<30;
gets(buff);
ind = 0;
dim = strlen(buff);
for(i=1; i<=N; ++i) {
V[i] = get_number(ind, dim);
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[dr] - Deque[st] >= k)
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;
}