Submission #1099729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099729		dzhoz0	Secret (JOI14_secret)	C++17	100 / 100	348 ms	4528 KiB

secret

/*
    ghmt the cutie :3
          UwU
*/

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

#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MAXN = 1000;
const int LG = 9;
int st[LG + 1][MAXN], mask[MAXN];
vi v;
void preprocess(int l, int r, int k, int a[]) {
    if(l == r) return;
    int mid = (l + r) / 2;
    st[k][mid] = a[mid];
    for(int i = mid - 1; i >= l; i--) st[k][i] = Secret(a[i], st[k][i + 1]);
    st[k][mid + 1] = a[mid + 1];
    for(int i = mid + 2; i <= r; i++) st[k][i] = Secret(st[k][i - 1], a[i]);

    for(int i = mid + 1; i <= r; i++) mask[i] ^= (1 << k);
   
    preprocess(l, mid, k + 1, a);
    preprocess(mid + 1, r, k + 1, a);
}

void Init(int n, int a[]) {
    preprocess(0, n - 1, 0, a);
    for(int i = 0; i < n; i++) v.push_back(a[i]);
}

int Query(int l, int r) {
    if(l == r) return v[l];
    int bits = __builtin_ctz(mask[l] ^ mask[r]);
    return Secret(st[bits][l], st[bits][r]);
}

• Subtask 1: 100 / 100