Mai intai trebuie sa te autentifici.
Cod sursa(job #97069)
Utilizator | Data | 4 noiembrie 2007 22:53:55 | |
---|---|---|---|
Problema | Secventa | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.74 kb |
#include<stdio.h>
int n, k, v[500005], i, first, last, max, p1, p2;
struct deque{
int v, i;
};
deque q[500005];
int main()
{
freopen("secventa.in", "rt", stdin);
freopen("secventa.out", "wt", stdout);
scanf("%d%d", &n, &k);
for (i=1; i<=n; i++)
scanf("%d", &v[i]);
q[1].v = v[1];
q[1].i = 1;
first = 1;
last = 1;
max = -30001;
for (i=2; i<=n; i++){
while (first <= last && i-q[first].i >= k)
first ++;
while (first <= last && v[i] <= q[last].v)
last --;
q[++last].v = v[i];
q[last].i = i;
if (q[first].v > max && q[last].i-q[first].i+1 >= k){
max = q[first].v;
p1 = q[first].i;
p2 = q[last].i;
}
}
printf("%d %d %d\n", p1, p2, max);
fclose(stdin);
fclose(stdout);
return 0;
}