제출 #971740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971740		Art_ogo	비밀 (JOI14_secret)	C++17	0 / 100	403 ms	4436 KiB

secret

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

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e3+10, LG = 10;

int msk[MAXN];
int t[LG][MAXN];
int a[MAXN];
int n;


void build(int l, int r, int v){
    if(l == r){
        t[v][l] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    t[v][m] = a[m];
    msk[m] ^= 1 << v;
    for(int i = m - 1; i >= l; i--){
        t[v][i] = Secret(a[i], t[v][i + 1]);
        msk[i] ^= 1 << v;
    }
    t[v][m + 1] = a[m + 1];
    for(int i = m + 2; i <= r; i++)
        t[v][i] = Secret(t[v][i - 1], a[i]);
    build(l, m, v + 1);
    build(m + 1, r, v + 1);
}


void Init(int N, int A[]){
    n = N;
    for(int i = 0; i < N; i++)
        a[i] = A[i];
    build(0, N - 1, 0);
}

int Query(int L, int R){
    if(L == R)
        return a[L];
    int cur = __builtin_ctz(msk[L]^msk[R]);
    return Secret(t[cur][L], t[cur][R]);
}

• Subtask 1: 0 / 100