Submission #1134749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134749		lopkus	Secret (JOI14_secret)	C++20	100 / 100	347 ms	4796 KiB

secret

#include<bits/stdc++.h>
#include "secret.h"

using namespace std;

#define pb push_back

const int MXN = 1003;

int n, a[MXN];
vector<int> pre[MXN<<2], suf[MXN<<2];

#define mid (l+r>>1)
#define lc id<<1
#define rc lc|1

void build(int l=0, int r=n, int id=1) {
  if(r-l==1) {
    pre[id].pb(a[l]);
    suf[id].pb(a[l]);
    return;
  }
  build(l, mid, lc);
  build(mid, r, rc);
  if(id==1) return;
  pre[id] = pre[lc];
  for(int i=mid; i<r; i++)
    pre[id].pb(Secret(pre[id].back(), a[i]));
  suf[id] = suf[rc];
  for(int i=mid-1; i>l; i--)
    suf[id].pb(Secret(a[i], suf[id].back()));
  suf[id].pb(pre[id].back());
}

void Init(int N, int A[]) {
  n = N;
  for(int i=0; i<n; i++) a[i] = A[i];
  build();
}

int get(int s, int e, int l=0, int r=n, int id=1) {
  if(r-l==1) return pre[id].back();
  if(e<=mid) return get(s, e, l, mid, lc);
  if(s>=mid) return get(s, e, mid, r, rc);
  return Secret(suf[lc][mid-s-1], pre[rc][e-mid-1]);
}

int Query(int L, int R) {
  return get(L, R+1);
}

• Subtask 1: 100 / 100