Cod sursa(job #1104745)

Utilizator vlad96Vlad Zuga vlad96 Data 10 februarie 2014 23:25:45
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <stdio.h>
#include <math.h>
#include <vector>

using namespace std;

const int N_MAX = 65560;
const int Log_MAX = 20;
int v[N_MAX * 2], n;
long long sol;
int lg[N_MAX * 2], rmq_min[Log_MAX][N_MAX * 2], rmq_max[Log_MAX][N_MAX * 2];

void read ()
{
    FILE *fis = fopen ("collar.in", "r");
    fscanf(fis, "%d", &n);
    for (int i = 1; i <= n; i ++ )
        fscanf(fis, "%d", &v[i]);
    for (int i = n+1; i < 2*n; i ++ )
        v[i] = v[i-n];
    fclose(fis);
}

void rmq()
{
    lg[1] = 0;
    for (int i = 2; i <= 2*n; i ++ )
        lg[i] = lg[i/2] + 1;
    for (int i = 1; i <= 2*n; i ++ )
        rmq_max[0][i] = v[i], rmq_min[0][i] = v[i];

    int l;
    for (int i = 1; (1<<i) <= 2*n; i ++ )
    {
        for (int j = 1; j + (1<<i) - 1 <= 2*n; j ++ )
        {
            l = 1 << (i-1);
            rmq_min[i][j] = min (rmq_min[i-1][j], rmq_min[i-1][j+l]);
            rmq_max[i][j] = max (rmq_max[i-1][j], rmq_max[i-1][j+l]);
        }
    }
}

inline int maxim(int i, int j)
{
    int k = lg[j - i + 1];
    return max (rmq_max[k][i], rmq_max[k][j-(1<<k)+1]);
}

inline int minim(int i, int j)
{
    int k = lg[j - i + 1];
    return min (rmq_min[k][i], rmq_min[k][j-(1<<k)+1]);
}

void solve ()
{
    int d1;
    long long temp;
    rmq();
    for (int d = 2; d <= sqrt(n); d ++ )
    {
        if ( n % d == 0 )
        {
            for (int i = 1; i <= d; i ++ )
            {
                temp = 0;
                for (int j = i + d-1; j <= i + n - 1; j += d )
                    temp += maxim (j-d+1, j) - minim (j-d+1, j), temp *= 1LL;
                if ( temp > sol )
                    sol = temp, sol *= 1LL;
            }
            d1 = n / d;
            for (int i = 1; i <= d1; i ++ )
            {
                temp = 0;
                for (int j = i + d1-1; j <= i + n - 1; j += d1 )
                    temp += maxim (j-d1+1, j) - minim (j-d1+1, j), temp *= 1LL;
                if ( temp > sol )
                    sol = temp, sol *= 1LL;
            }
        }
    }
}

void write ()
{
    FILE *fis2 = fopen ("collar.out", "w");
    fprintf(fis2, "%lld\n", sol);
    fclose(fis2);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}