Submission #1261459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261459		thecyb	Secret (JOI14_secret)	C++17	100 / 100	415 ms	4468 KiB

secret

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#include "secret.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) {
  if (l == r) {
  return;
  }
  int m = (l + r) >> 1;
  dnc[lvl][m] = arr[m];
  dnc[lvl][m+1] = arr[m+1];
  for (int i = m-1; i >= l; i--) dnc[lvl][i] = Secret(arr[i], dnc[lvl][i+1]);
  for (int i = m+2; i <= r; i++) dnc[lvl][i] = Secret(dnc[lvl][i-1], arr[i]);
  for (int i = m+1; i <= r; i++) mask[i] ^= 1<<lvl;
  divide_conquer(lvl+1, l, m);
  divide_conquer(lvl+1, m+1, r);
}

void Init(int n, int a[]) {
  memset(dnc, 0, sizeof dnc);
  for (int i = 0; i < n; i++) arr[i] = a[i];
  divide_conquer(0, 0, n-1);
}

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]);
}

• Subtask 1: 100 / 100