제출 #56554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56554		ruhanhabib39	Secret (JOI14_secret)	C++17	100 / 100	681 ms	13688 KiB

secret

#include "secret.h"
#include <algorithm>
using namespace std;

namespace {
   const int MAXN = 1000;
   int pref[4*MAXN + 10][MAXN + 10], suff[4*MAXN + 10][MAXN + 10];
   int *A, N;
   void build(int cn, int b, int e) {
      if(b == e) return;
      int m = (b + e) / 2;
      int L = cn << 1, R = L | 1;
      suff[L][m] = A[m];
      for(int i = m-1; i >= b; i--) {
         suff[L][i] = Secret(A[i], suff[L][i+1]);
      }
      pref[R][m+1] = A[m+1];
      for(int i = m+2; i <= e; i++) {
         pref[R][i] = Secret(pref[R][i-1], A[i]);
      }
      build(L, b, m); build(R, m+1, e);
   }
};

void Init(int N_, int *A_) {
   N = N_;
   A = A_;
   build(1, 0, N-1);
   pref[1][N-1] = Secret(suff[2][0], pref[3][N-1]);
}

int Query(int l, int r) {
   int cn = 1, b = 0, e = N-1;
   while(true) {
      if(l == b && r == e) {
         if(cn & 1) return pref[cn][r];
         else return suff[cn][l];
      }
      int m = (b + e) / 2;
      if(l <= m && m <= r) {
         if(r == m) return suff[cn<<1][l];
         else return Secret(suff[cn<<1][l], pref[cn<<1|1][r]);
      }
      if(r <= m) {
         cn = cn << 1;
         e = m;
      } else {
         cn = cn<<1 | 1;
         b = m+1;
      }
   }
}

• Subtask 1: 100 / 100