Pagini recente » Cod sursa (job #538974) | Cod sursa (job #936234) | Cod sursa (job #2695014) | Cod sursa (job #727557) | Cod sursa (job #65140)
Cod sursa(job #65140)
#include <assert.h>
#include <stdio.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++;
assert(end > 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;
}
}
assert(best != -inf);
}
int main()
{
int i;
FILE *f = fopen("secventa.in", "r");
if(!f) return 1;
fscanf(f, "%d%d", &n, &len);
for(i = 0; i < n; i++)
fscanf(f, "%d", &p[i]);
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;
}