Submission #113468

#	Time	Username	Problem	Language	Result	Execution time	Memory
113468		popovicirobert	Secret (JOI14_secret)	C++14	100 / 100	504 ms	8520 KiB

secret

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

using namespace std;

const int MAXN = 1000;

int mat[MAXN][MAXN], n;

void divide(int l, int r, int *A) {

    if(l == r) {
        mat[l][r] = A[l];
        return ;
    }

    int mid = (l + r) / 2;

    mat[mid][mid] = A[mid];

    for(int i = mid - 1; i >= l; i--) {
        mat[i][mid] = Secret(A[i], mat[i + 1][mid]);
    }

    mat[mid + 1][mid + 1] = A[mid + 1];

    for(int i = mid + 2; i <= r; i++) {
        mat[mid + 1][i] = Secret(mat[mid + 1][i - 1], A[i]);
    }

    divide(l, mid, A);
    divide(mid + 1, r, A);

}

void Init(int N, int A[]) {
    n = N;
    divide(0, N - 1, A);
}

int solve(int l, int r, int ql, int qr) {
    int mid = (l + r) / 2;

    if(ql <= mid && mid < qr) {
        return Secret(mat[ql][mid], mat[mid + 1][qr]);
    }

    if(qr <= mid) {
        return solve(l, mid, ql, qr);
    }
    return solve(mid + 1, r, ql, qr);

}

int Query(int l, int r) {

    if(l == r) {
        return mat[l][l];
    }

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

• Subtask 1: 100 / 100