Submission #867141

#	Time	Username	Problem	Language	Result	Execution time	Memory
867141		bobbilyking	Secret (JOI14_secret)	C++17	100 / 100	381 ms	4764 KiB

secret

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

using ll=int;
ll a[1010];

struct tree {
  ll l, r, m;
  tree* c[2];
  vector<ll> left, right;
  tree(ll l, ll r): l(l), r(r), m((l+r)/2) {
    if (l<r) {
        if (l <= m-1) c[0] = new tree(l, m-1); else c[0] = nullptr;
        if (m + 1 <= r) c[1] = new tree(m+1, r); else c[1] = nullptr;
        {
          // [l, m-1] but stored in reverse order (length ig)
          left.push_back(a[m-1]);
          for (ll i = m-2; i >= l; --i) left.push_back(Secret(a[i], left.back()));
        }
        {
          // [m, r]
          right.push_back(a[m]);
          for (ll i = m+1; i <= r; ++i) right.push_back(Secret(right.back(), a[i]));
        }

    }
  }

  ll query(ll ql, ll qr) {
    if (ql <= m and m <= qr) {
        if (ql == m) {
          // only need right
          return right[qr-m];
        } else {
          return Secret(left[m-ql-1], right[qr-m]);
        }
    } else if (ql < m) return c[0]->query(ql, qr); 
    else return c[1]->query(ql, qr);
  }

}* root;

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

int Query(int L, int R) {
  if (L == R) return a[L];
  else return root->query(L, R);
}

• Subtask 1: 100 / 100