Submission #349937

#	Time	Username	Problem	Language	Result	Execution time	Memory
349937		blue	Secret (JOI14_secret)	C++11	6 / 100	1012 ms	8424 KiB

secret

#include "secret.h"
#include <iostream>
#include <vector>
using namespace std;




//midpoint, endpoint
int res[1000][1000];

int N;
vector<int> A(1000);

void precompute(int a, int b)
{
    if(a == b)
    {
        res[a][a] = A[a];
        return;
    }
    if(a+1 == b)
    {
        res[a][b] = A[b];
        res[a][a] = A[a];
        return;
    }

    int m = (a+b)/2;

    res[m][m+1] = A[m+1];
    for(int i = m+2; i <= N-1; i++) res[m][i] = Secret(res[m][i-1], A[i]);

    res[m][m] = A[m];
    for(int i = m-1; i >= 0; i--) res[m][i] = Secret(A[i], res[m][i+1]);

    precompute(a, m);
    precompute(m+1, b);
}

void Init(int n, int a[])
{
    N = n;
    for(int i = 0; i < N; i++) A[i] = a[i];

    precompute(0, N-1);
}



int query1(int L, int R, int a, int b)
{
    int m = (a+b)/2;
    if(L <= m && m+1 <= R) return Secret(res[m][L], res[m][R]);
    else if(R <= m) return query1(L, R, a, m);
    else return query1(L, R, m+1, b);
}

int Query(int L, int R)
{
    if(L == R) return A[L];
    if(L+1 == R) return Secret(A[L], A[R]);
    return query1(L, R, 0, N-1);
}

• Subtask 1: 6 / 100