Cod sursa(job #42756)

Utilizator cretuMusina Rares cretu Data 29 martie 2007 14:57:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#define INF 999999
#define MAX 500001

using namespace std;

int a[MAX];
int n, k;

void update(int nod, int st, int dr, int p, int v);
int querry(int nod, int st, int dr, int a1, int b);
int minim(int x, int y);

int main()
{
    int i, j, max = 0, min, maxi, maxs, x;
    
    memset(a, INF, sizeof(a));
    
    ifstream fin("secventa.in");
    fin >> n >> k;
    for (i = 1; i <= n; i++)    
    {
        fin >> x;
        update(1, 1, n, i, x);
    }    
    fin.close();
    
    for (i = 1; i <= n-k+1; i++)
        for (j = i+k-1; j <= n; j++)
        {
            min = querry(1, 1, n, i, j);
            if (min > max) 
            {
                max = min;
                maxi = i;
                maxs = j;    
            }    
        }    
    
    ofstream fout("secventa.out");
    fout << maxi << " " << maxs << " " << max;
    fout.close();
    
    return 0;
}

void update(int nod, int st, int dr, int p, int v)
{
    int m = (st+dr)/2;
    if (st == dr)    
    {
        a[nod] = v;
        return;    
    }
    if (p <= m) update(2*nod, st, m, p, v);
    else        update(2*nod+1, m+1, dr, p, v);
    
    int min = minim(a[2*nod], a[2*nod+1]);
    
    if (a[nod] > min) a[nod] = min;
}

int querry(int nod, int st, int dr, int a1, int b)
{
    if (a1 <= st && dr <= b) return a[nod];
    int m = (st+dr)/2, s1 = INF, s2 = INF;
    if (a1 <= m) s1 = querry(2*nod, st, m, a1, b);
    if (m < b) s2 = querry(2*nod+1, m+1, dr, a1, b);   
    
    return minim(s1, s2);
}

int minim(int x, int y)
{
    return (x < y) ? x : y;    
}