Submission #554591

#	Time	Username	Problem	Language	Result	Execution time	Memory
554591		status_coding	Secret (JOI14_secret)	C++14	100 / 100	451 ms	4412 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;

int a[1005];
int dp[10][1005];

void calc(int st, int dr, int p)
{
    if(st >= dr)
        return;

    int mij = (st + dr)/2;
    //cout<<st<<' '<<dr<<' '<<mij<<'\n';

    dp[p][mij-1] = a[mij-1];
    for(int i=mij-2; i>=st; i--)
        dp[p][i] = Secret(a[i], dp[p][i+1]);

    dp[p][mij] = a[mij];
    for(int i=mij+1; i<=dr; i++)
        dp[p][i] = Secret(dp[p][i-1], a[i]);

    calc(st, mij-1, p+1);
    calc(mij+1, dr, p+1);
}

int query(int stt, int drt, int st, int dr, int p)
{
    int mij = (st+dr)/2;

    if(drt < mij)
        return query(stt, drt, st, mij-1, p+1);
    if(stt > mij)
        return query(stt, drt, mij+1, dr, p+1);

    if(stt == mij)
        return dp[p][drt];
    else
        return Secret(dp[p][stt], dp[p][drt]);
}

void Init(int N, int A[])
{
    n = N;

    for(int i=0;i<n;i++)
        a[i] = A[i];

    //cout<<"build\n";
    calc(0, n-1, 1);

    /*
    cout<<"debug\n";

    for(int i=0;i<n;i++)
        cout<<dp[1][i]<<' ';
    cout<<"\n\n";
    */
}

int Query(int l, int r)
{
    if(l == r)
        return a[l];

    return query(l, r, 0, n-1, 1);
}

• Subtask 1: 100 / 100