Cod sursa(job #471853)

Utilizator idomiralinIdomir Alin idomiralin Data 21 iulie 2010 14:29:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
# include <stdlib.h>
# include <cstdio>

using namespace std;

int n, k, front, back, a[500005], deque[500005], max, pozmax, bestpoz;
int main()
{int i;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    
    scanf("%d%d",&n,&k);
    
    for (i = 1; i <= n; i++)
    scanf("%d",&a[i]);
    
    front = 1; back = 0; max = -1000; pozmax = -1000;
    for (i = 1; i <= n; i++)
    {
        while (front <= back && a[i] < a[deque[back]]) back --;
        
        deque[++back] = i;
        
        if (deque[front] == i - k) front ++;
        
        
        if (i >= k) 
           {
        
        if (a[deque[front]] > max && front <= n - k + 1) 
                            {
                              pozmax = deque[front];
                              max = a[deque[front]];
                             }
        }
        if (pozmax == 1) bestpoz = 1;
        if (pozmax == 2) bestpoz = 1;
        if (pozmax == n - 1) bestpoz = n - 2;
        if (pozmax == n) bestpoz = n - 2;
        if (pozmax > 2 && pozmax < n -1)
        {
                   if (a[pozmax - 2] > a[pozmax] && a[pozmax - 1] > a[pozmax] ) bestpoz = pozmax - 2;
                   else if (a[pozmax - 1] > a[pozmax] && a[pozmax + 1] > a[pozmax]) bestpoz = pozmax - 1;
                   else if (a[pozmax + 1] > a[pozmax] && a[pozmax + 2] > a[pozmax]) bestpoz = pozmax;                   
         }
         }
        printf("%d %d %d", bestpoz, bestpoz + k - 1, max);
        
return 0;
}