oj.uz

Submission #757833

# Submission time Handle Problem Language Result Execution time Memory
757833 2023-06-13T19:13:27 Z taher Secret (JOI14_secret) C++17
100 / 100
 494 ms 36484 KB 
#include <bits/stdc++.h>

#include "secret.h"

using namespace std;

const int MaxN = 1005;
const int inf = 1234567890;

vector<vector<int>> calcPrev(4 * MaxN, vector<int> (MaxN)), calcNext(4 * MaxN, vector<int> (MaxN));
vector<int> at(MaxN, inf);
int n;
vector<int> a(MaxN);

void Init(int N, int A[]) {
  n = N;
  for (int i = 0; i < n; i++) a[i] = A[i];
  function<void(int, int, int)> Divide = [&](int cnt, int low, int high) {
    if (low > high) {
      return ;
    }
    int mid = low + (high - low) / 2;
    int cur = a[mid];
    at[mid] = cnt;
    calcPrev[cnt][mid] = cur;
    for (int i = mid - 1; i >= low; i--)  {
      cur = Secret(a[i], cur);
      calcPrev[cnt][i] = cur;
    }
    if (mid < high) {
      cur = a[mid + 1];
      calcNext[cnt][mid + 1] = cur;
      for (int i = mid + 2; i <= high; i++) {
        cur = Secret(cur, a[i]);
        calcNext[cnt][i] = cur;
      }
    }
    Divide(2 * cnt, low, mid - 1);
    Divide(2 * cnt + 1, mid + 1, high);
    return ;
  };
  Divide(1, 0, n - 1);
}

int Query(int L, int R) {
  int l = L, r = R;
  int mnId = inf;
  int it = -1;
  for (int i = l; i <= r; i++) {
    if (mnId > at[i]) {
      it = i;
      mnId = at[i];
    }
  }
  int cur = calcPrev[mnId][l];
  if (r > it) {
    cur = Secret(cur, calcNext[mnId][r]);
  }
  return cur;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 34252 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 34368 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 34488 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 439 ms 36256 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 456 ms 36484 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 475 ms 36196 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 478 ms 36156 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 450 ms 36256 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 467 ms 36196 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 494 ms 36268 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1