Submission #236659

#	Time	Username	Problem	Language	Result	Execution time	Memory
236659		DS007	Secret (JOI14_secret)	C++14	100 / 100	510 ms	9464 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
 
const int N_ = 1000;
int val[N_][N_];
bool done[N_][N_];
 
int n, *a;
 
void pre(int l, int r) {
    if (l == r)
        return;
 
    int mid = (l + r) / 2;
    for (int i = mid - 1, temp = a[mid]; i >= l; i--) {
        if (done[i][mid]) {
            temp = val[i][mid];
            continue;
        }
 
        temp = Secret(a[i], temp);
        val[i][mid] = temp;
        done[i][mid] = true;
    }
 
    for (int i = mid + 2, temp = a[mid + 1]; i <= r; i++) {
        if (done[mid + 1][i]) {
            temp = val[mid + 1][i];
            continue;
        }
 
        temp = Secret(temp, a[i]);
        val[mid + 1][i] = temp;
        done[mid + 1][i] = true;
    }
 
    pre(l, mid);
    pre(mid + 1, r);
}
 
void Init(int N, int A[]) {
    n = N;
    a = A;
 
    for (int i = 0; i < n; i++)
        val[i][i] = a[i], done[i][i] = true;
 
    pre(0, n - 1);
}
 
int query_util(int l, int r, int tl, int tr) {
    int mid = (l + r) / 2;
    if (tl <= mid && mid < tr)
        return Secret(val[tl][mid], val[mid + 1][tr]);
    else if (tr <= mid)
        return query_util(l, mid, tl, tr);
    else
        return query_util(mid + 1, r, tl, tr);
}
 
int Query(int L, int R) {
    if (done[L][R])
        return val[L][R];
    return query_util(0, n - 1, L, R);
}

• Subtask 1: 100 / 100