Pagini recente » Cod sursa (job #747910) | Cod sursa (job #136408) | Cod sursa (job #1266132) | Cod sursa (job #980639) | Cod sursa (job #65143)
Cod sursa(job #65143)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { maxn = 500001, inf = 0x3F3F3F3F };
int n, len;
int p[maxn];
int best, best_start, best_end;
int start, end;
int deq[maxn];
int pos[maxn]; //pos of deq[i] in p[]
void go()
{
int i, seqstart;
best = -inf;
for(i = 0; i < n; i++)
{
//pop_back() until it's the maximum
while(end > start && deq[end - 1] > p[i])
end--;
//add p[i]
deq[end] = p[i];
pos[end] = i;
end++;
//pop_front() until pos[end] - pos[start] is short enough
while(start < end && pos[end - 1] - pos[start] >= len)
start++;
//the sequence may start anywhere between the previous-to-start minimum and start
if(start > 0)
seqstart = pos[start - 1] + 1;
else
seqstart = 0;
//update ans
if(pos[end - 1] - seqstart >= len - 1 && deq[start] > best)
{
best = deq[start];
best_start = seqstart;
best_end = seqstart + len - 1;
}
}
}
int main()
{
int i;
char buf[maxn * 7], *s = buf;
size_t stupid_getline = maxn * 7 - 1;
FILE *f = fopen("secventa.in", "r");
if(!f) return 1;
fscanf(f, "%d %d\n", &n, &len);
getline(&s, &stupid_getline, f);
for(i = 0; i < n; i++)
{
if(i != 0) s++; //the space
p[i] = atoi(s);
s = strchr(s, ' ');
}
fclose(f);
f = fopen("secventa.out", "w");
if(!f) return 1;
go();
fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
fclose(f);
return 0;
}