Pagini recente » Cod sursa (job #2104046) | Istoria paginii runda/moisil2011 | Cod sursa (job #198981) | Istoria paginii utilizator/sava_barbuta_dospra | Cod sursa (job #97846)
Cod sursa(job #97846)
#include <stdio.h>
#include <stdlib.h>
int stack[500001];
int poz[500001];
int begin, end;
void add(int& v, int& pozitie)
{
int i = begin;
while(stack[i] < v && i < end)
{
++i;
}
if(stack[i] >= v)
{
stack[i] = v;
}
else
{
stack[++i] = v;
}
poz[i] = pozitie;
end = i;
}
void print()
{
for(int i=begin;i<=end;++i)
printf("(%d / %d) ", stack[i], poz[i]);
printf("\n");
}
int main(void)
{
FILE* fin;
FILE* fout;
fin = fopen("secventa.in", "r");
fout = fopen("secventa.out", "w");
int n, k;
fscanf(fin, "%d %d\n", &n, &k);
int max = -30001;
int start = -1;
begin = 0;
end = 0;
stack[0] = 300001;
for(int i=0;i<n;++i)
{
int v;
fscanf(fin, "%d ", &v);
add(v, i);
if(i>=k-1)
{
// print();
while(i-poz[begin] > k-1)
++begin;
if(stack[begin] > max)
{
max = stack[begin];
start = i-(k-1);
}
}
}
fclose(fin);
fprintf(fout, "%d %d %d\n", start+1, start+1+k-1, max);
fclose(fout);
return 0;
}