Submission #25344

#	Time	Username	Problem	Language	Result	Execution time	Memory
25344		kajebiii	Secret (JOI14_secret)	C++14	100 / 100	633 ms	19292 KiB

secret

#include "secret.h"
#include <vector>
#include <stdio.h>

using namespace std;

const int MAX_N = 1e3 + 100;
const int ROOT_N = 32;

int Nr[MAX_N], W[MAX_N][MAX_N], Cnt;
int L[MAX_N][MAX_N], R[MAX_N][MAX_N];

void makeLR(int a, int b) {
    if(a == b) return;
    int m = (a+b) >> 1;
    Cnt++;
    for(int i=a; i<=m; i++) for(int j=m+1; j<=b; j++)
        W[i][j] = Cnt;
    L[Cnt][m] = Nr[m];
    R[Cnt][m+1] = Nr[m+1];
    for(int i=m-1; i>=a; i--) L[Cnt][i] = Secret(Nr[i], L[Cnt][i+1]);
    for(int i=m+2; i<=b; i++) R[Cnt][i] = Secret(R[Cnt][i-1], Nr[i]);
    makeLR(a, m);
    makeLR(m+1, b);
}
int getQ(int a, int b) {
    if(a == b) return Nr[a];
    int w = W[a][b];
    return Secret(L[w][a], R[w][b]);
}
void Init(int N, int A[]) {
    for(int i=0; i<N; i++) Nr[i] = A[i];
    makeLR(0, N-1);
}

int Query(int L, int R) {
    return getQ(L, R);
}

• Subtask 1: 100 / 100