oj.uz

Submission #867141

# Submission time Handle Problem Language Result Execution time Memory
867141 2023-10-27T18:07:30 Z bobbilyking Secret (JOI14_secret) C++17
100 / 100
 381 ms 4764 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2644 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
2 Correct 103 ms 2652 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
3 Correct 104 ms 2904 KB Output is correct - number of calls to Secret by Init = 3358, maximum number of calls to Secret by Query = 1
4 Correct 377 ms 4476 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
5 Correct 366 ms 4764 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1
6 Correct 363 ms 4468 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1
7 Correct 364 ms 4616 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1
8 Correct 381 ms 4600 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1
9 Correct 365 ms 4692 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1
10 Correct 361 ms 4600 KB Output is correct - number of calls to Secret by Init = 7507, maximum number of calls to Secret by Query = 1