Cod sursa(job #539444)

Utilizator idomiralinIdomir Alin idomiralin Data 22 februarie 2011 22:35:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
# include <cstdio>
# include <cstdlib>
# include <fstream>

using namespace std;

int n, k, i, semn, front, back, sum, pozi, pozf, a[500005], deque[500005], aux, poz;
char s[500005];
int main()
{int max;
    ifstream in("secventa.in");
    ofstream out("secventa.out");
    
    in>>n>>k;
    for (i = 1; i <= n; i++)
    in>>a[i];
    
    /*for (i = 1; i <= n; i++) 
    {
        scanf("%s",s);
    for (i = 0; s[i]; ++i)
    if (s[i] == '-') semn = 1;
                else aux = aux * 10 + s[i] - '0';
                
    if (semn) a[++poz] = -aux;
       else a[++poz] = aux;       
       aux = 0; semn = 0;
    }
    */
    front = 1; back = 0; max = -500005;
    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 && max < a[deque[front]])
        {
              max = a[deque[front]];
              pozi = i - k + 1;
              pozf = i;
              }           
        }
        
        out<<pozi<<" "<<pozf<<" "<<max;
    
return 0;
}