Submission #1269138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269138		uranium235	Secret (JOI14_secret)	C++17	0 / 100	346 ms	4528 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dnc(10, vector<int>(1000));
vector<vector<int>> cnd(10, vector<int>(1000));

void divide(int l, int r, int v, int *a) {
    if (l == r) dnc[v][l] = a[l];
    else {
        int m = (l + r) / 2;
        divide(l, m, v + 1, a);
        divide(m + 1, r, v + 1, a);
        dnc[v][l] = a[l];
        for (int i = l + 1; i <= m; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
        dnc[v][m + 1] = a[m + 1];
        for (int i = m + 2; i <= r; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
        cnd[v][m] = a[m];
        for (int i = m - 1; i >= l; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
        cnd[v][r] = a[r];
        for (int i = r - 1; i > m; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
    }
}

int nn;
int conquer(int ll, int rr, int l, int r, int v) {
    // cout << "dividng " << l << " " << r << endl;
    if (l == r) return dnc[v][l];

    int m = (l + r) / 2;
    if (rr <= m) return conquer(ll, rr, l, m, v + 1);
    else if (ll > m) return conquer(ll, rr, m + 1, r, v + 1);
    
    return Secret(cnd[v][ll], dnc[v][rr]);
}

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

int Query(int l, int r) {
    // cout << "query" << endl;
    return conquer(l, r, 0, nn - 1, 0);
}

• Subtask 1: 0 / 100