Submission #1294162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294162		papaulo	Secret (JOI14_secret)	C++20	100 / 100	342 ms	4472 KiB

secret

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

#define MAXN 1010
#define MAXD 15
int x[MAXN];
int suf[MAXD][MAXN];
int pref[MAXD][MAXN];
int n;

void dqc(int l, int r, int d) {
  if(l>r) return;
  int mid=(l+r)/2;
  dqc(l, mid-1, d+1);
  dqc(mid+1, r, d+1);
  suf[d][mid]=x[mid];
  if(mid+1<=r) pref[d][mid+1]=x[mid+1];
  for(int i=mid-1;i>=l;i--) suf[d][i]=Secret(x[i], suf[d][i+1]);
  for(int i=mid+2;i<=r;i++) pref[d][i]=Secret(pref[d][i-1], x[i]);
}

int query(int l, int r, int p, int q, int d) {
  int mid=(l+r)/2;
  if(q<mid) return query(l, mid-1, p, q, d+1);
  if(p>mid) return query(mid+1, r, p, q, d+1);
  if(q==mid) return suf[d][p];
  return Secret(suf[d][p], pref[d][q]);
}

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

int Query(int L, int R) {
  return query(0, n-1, L, R, 0);
}

• Subtask 1: 100 / 100