Submission #1025320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025320		a5a7	Secret (JOI14_secret)	C++14	100 / 100	333 ms	4444 KiB

secret

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

vector<vector<int>> v; int c;
vector<int> arr;
vector<int> mask;

void create(int left, int right, int depth){
    if (depth > 8) return;
    if (left == right){
        v[depth][left] = arr[left];
        return;
    }
    int mid = (left+right)/2;
    v[depth][mid] = arr[mid];
    v[depth][mid+1] = arr[mid+1];
    for (int i = mid-1; i >= left; i--) v[depth][i] = Secret(arr[i], v[depth][i+1]);
    for (int i = mid+2; i <= right; i++) v[depth][i] = Secret(v[depth][i-1], arr[i]);
    for (int i = mid+1; i <= right; i++) mask[i] ^= (1<<(c-depth-1));
    create(left, mid, depth+1);
    create(mid+1, right, depth+1);
}

void Init(int n, int a[]) {
    c = 0;
    while ((1<<c) < n) c++;
    arr = vector<int>(n);
    for (int i = 0; i < n; i++) arr[i] = a[i];
    mask = vector<int>(n, 0);
    v = vector<vector<int>>(c+2, vector<int>(n, 0));
    create(0, n-1, 0);
}

int Query(int left, int right) {
    if (left == right) return arr[left];
    if (left == (right-1)) return Secret(arr[left], arr[right]);
    int t = c-(32-(__builtin_clz(mask[left]^mask[right])));
    return Secret(v[t][left], v[t][right]);
}

• Subtask 1: 100 / 100