Cod sursa(job #929649)

Utilizator rudarelLup Ionut rudarel Data 27 martie 2013 10:17:11
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
 
#define NMAX 500001
#define MIN -30001
 
int n, k, x[NMAX], poz[NMAX], q[NMAX];
int max, msf;
 
int toint(char s[]) {
    int r, i;
     
    for (r = 0, i = s[0] == '-' ? 1 : 0; s[i] >= '0' && s[i] <= '9'; ++i)
        r = r * 10 + (s[i] - '0');
     
    return s[0] == '-' ? -r : r;
}
 
void read()
{
    char s[16];
    int i;
    scanf("%s", s);
    n = toint(s);
    scanf("%s", s);
    k = toint(s);
     
    for (i = 1; i <= n; i++) {
        scanf("%s", s);
        x[i] = toint(s);
    }
}
 
void rezolv()
{
    int i, beg, end;
    beg = end = 1; q[1] = x[1]; poz[1] = 1;
    max = MIN;
 
    for (i = 2; i <= n; i++)
    {
        if (poz[beg] + k <= i)
            beg++;
             
        for (; x[i] < q[end] && end >= beg; --end);
        q[++end] = x[i], poz[end] = i;
         
        if (i >= k && q[beg] > max)
            max = q[beg], msf = i;
    }  
}
 
void afisare()
{
    int p;
    for (p = msf - k; p > 0 && x[p] >= max; --p);
    printf("%d %d %d\n", p + 1, msf, max);
}
 
int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    read();
    rezolv();
    afisare();
    return 0;
}