# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1261445 | thecyb | 비밀 (JOI14_secret) | C++17 | 0 ms | 0 KiB |
/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
int dnc[11][1024], mask[1024];
int arr[1024];
void divide_conquer(const int &lvl, const int &l, const int &r, int a[]) {
if (l == r) return;
int m = (l + r) >> 1;
dnc[lvl][m] = a[m];
dnc[lvl][m+1] = a[m+1];
for (int i = m-1; i >= 0; i--) dnc[lvl][i] = Secret(a[i], dnc[lvl][i+1]);
for (int i = m+2; i < r; i++) dnc[lvl][i] = Secret(a[i], dnc[lvl][i-1]);
for (int i = m+1; i < r; i++) mask[i] ^= 1<<lvl;
divide_conquer(lvl+1, l, m, a);
divide_conquer(lvl+1, m+1, r, a);
}
void init(int n, int a[]) {
memset(dnc, 0, sizeof dnc);
memcpy(arr, a, sizeof arr);
divide_conquer(0, 0, n-1, a);
}
int Query(int l, int r) {
if (l == r) return arr[l];
int lvl = __builtin_ctz(mask[l] ^ mask[r]);
return Secret(dnc[lvl][l], dnc[lvl][r]);
}