Submission #246295

#	Time	Username	Problem	Language	Result	Execution time	Memory
246295		Coroian_David	Secret (JOI14_secret)	C++11	100 / 100	532 ms	4600 KiB

secret

#include <bits/stdc++.h>

#include "secret.h"

#define MAX_N 1000
#define MAX_LOG 10

using namespace std;

int v[MAX_N + 1];

int dp[MAX_LOG + 1][MAX_N + 1];

int mi[MAX_LOG + 1];
int Secret(int X, int Y);

void divide(int st, int dr, int niv)
{
    if(st >= dr)
        return;

      //  cout << " FACEM DIVITE " << st << " " << dr << " " << niv << "\n";

    if(st == dr - 1)
    {
        dp[niv][st] = v[st];
        dp[niv][dr] = v[dr];

        return;
    }

    int mid = (st + dr) >> 1;
    mi[niv] = mid;

    dp[niv][mid] = v[mid];
    for(int i = mid - 1; i >= st; i --)
    {
        dp[niv][i] = Secret(v[i], dp[niv][i + 1]);
       // cout << "la " << i << " este " << dp[niv][i] << " ";
    }

    dp[niv][mid + 1] = v[mid + 1];
    for(int i = mid + 2; i <= dr; i ++){
        dp[niv][i] = Secret(dp[niv][i - 1], v[i]);
       // cout << "la " << i << " este " << dp[niv][i] << " ";
    }

    divide(st, mid, niv + 1);
    divide(mid + 1, dr, niv + 1);
}

int n;

void Init(int N, int A[])
{
    n = N;
    for(int i = 1; i <= n; i ++)
        v[i] = A[i - 1];

    divide(1, n, 0);
}

int getRez(int st, int dr, int a, int b, int niv)
{
    if(st == dr)
        return v[st];

    int mid = (st + dr) >> 1;

    //cout << " GETREZ " << st << " " << dr << " " << mid << " " << niv <<" \n";

    if(b <= mid)
        return getRez(st, mid, a, b, niv + 1);

    if(a > mid)
        return getRez(mid + 1, dr, a, b, niv + 1);

   // cout << " ESTE SECRET " << dp[niv][st] << " " << dp[niv][dr] << "\n";

    return Secret(dp[niv][a], dp[niv][b]);
}

int Query(int L, int R)
{
    return getRez(1, n, L + 1, R + 1, 0);
}

• Subtask 1: 100 / 100