oj.uz

Submission #961410

# Submission time Handle Problem Language Result Execution time Memory
961410 2024-04-12T04:25:41 Z aufan Secret (JOI14_secret) C++17
100 / 100
 373 ms 9400 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) {
  int cnt = 10;
  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);
}

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:40:7: warning: unused variable 'cnt' [-Wunused-variable]
   40 |   int cnt = 10;
      |       ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7516 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 105 ms 7668 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 112 ms 7684 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 367 ms 9232 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 373 ms 9400 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 365 ms 9232 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 367 ms 9228 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 364 ms 9296 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 361 ms 9300 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 9336 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1