Pagini recente » Cod sursa (job #1167877) | Cod sursa (job #3215380) | Cod sursa (job #2431585) | Cod sursa (job #1715221) | Cod sursa (job #65124)
Cod sursa(job #65124)
#include <assert.h>
#include <stdio.h>
#define printf(...) /* shut up */
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;
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++;
//push_front() until pos[end] - pos[start] is short enough
while(start < end && pos[end - 1] - pos[start] >= len)
start++;
{
//debug
printf("p[%d] %d. deq: ", i, p[i]);
assert(end > start);
for(int i = start; i < end; i++)
{
printf("%d (pos %d), ", deq[i], pos[i]);
assert(p[ pos[i] ] == deq[i]);
}
printf("\b\b\n");
}
assert(end > start);
//update ans
if(pos[end - 1] - pos[start] == len - 1 && deq[start] > best)
{
best = deq[start];
best_start = pos[start];
best_end = pos[end - 1];
printf("updated best to %d, start %d end %d\n", best, best_start, best_end);
}
else if(end - 1 == start && i >= len - 1 && p[i] > best)
{
//no maximums so far => everything before me is bigger => I'm the minimum
best = p[i];
best_start = i - len + 1;
best_end = i;
printf("funky shit best %d, start %d end %d\n", best, best_start, best_end);
}
}
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;
}