Submission #1146182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146182		Newtonabc	Secret (JOI14_secret)	C++20	6 / 100	676 ms	8352 KiB

secret

#include "secret.h"
int dp[1010][1010];
//ans from i to j(mid)
int n;
void solve(int l,int r){
  if(l+1>=r) return;
  int m=(l+r)/2;
  int suf=dp[m][m],pre=dp[m+1][m+1];
  for(int i=m-1;i>=0;i--){
    suf=Secret(dp[i][i],suf);
    dp[i][m]=suf;
  }
  for(int i=m+2;i<n;i++){
    pre=Secret(pre,dp[i][i]);
    dp[i][m+1]=pre;
  }
  solve(l,m);
  solve(m+1,r);
}

int find(int l,int r,int a,int b){
  int m=(l+r)/2;
  if(b<=m) return find(l,m,a,b);
  if(a>=m+1) return find(m+1,r,a,b);
  return Secret(dp[a][m],dp[b][m+1]);
}

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

int Query(int L, int R) {
  if(L==R) return dp[L][L];
  return find(0,n-1,L,R);
}

• Subtask 1: 6 / 100