oj.uz

Submission #961411

# Submission time Handle Problem Language Result Execution time Memory
961411 2024-04-12T04:26:22 Z aufan Secret (JOI14_secret) C++17
100 / 100
 363 ms 9296 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a(1111);
vector<vector<int>> val(1111, vector<int>(1111, -1));

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

  function<void(int, int)> dnc = [&](int lf, int rg) {  
    if (rg - lf + 1 <= 2) return;

    int md = (lf + rg) / 2;
    for (int i = md - 1; i >= lf; i--) {
      if (val[i][md] == -1) {
        val[i][md] = Secret(a[i], val[i + 1][md]);
      }
    }
    for (int i = md + 2; i <= rg; i++) {
      if (val[md + 1][i] == -1) {
        val[md + 1][i] = Secret(val[md + 1][i - 1], a[i]);
      }
    }

    dnc(lf, md);
    dnc(md + 1, rg);
  };

  dnc(0, n - 1);
}

int Query(int l, int r) {
  function<int(int, int)> dnc = [&](int lf, int rg) {
    if (val[l][r] != -1) return val[l][r];

    int md = (lf + rg) / 2;
    if (l > md) {
      return dnc(md + 1, rg);
    } else if (r < md + 1) {
      return dnc(lf, md);
    } else {
      return Secret(val[l][md], val[md + 1][r]);
    }
  };

  return dnc(0, n - 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 7512 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 103 ms 7608 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 7504 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 359 ms 9296 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 362 ms 9044 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 357 ms 9268 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 362 ms 9044 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 360 ms 9284 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 363 ms 9052 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 361 ms 9072 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1