oj.uz

Submission #125937

# Submission time Handle Problem Language Result Execution time Memory
125937 2019-07-06T14:46:02 Z AlexLuchianov Secret (JOI14_secret) C++14
100 / 100
 607 ms 8520 KB 
#include "secret.h"
#include <iostream>


int const nmax = 1000;

//int Secret(int X, int Y)

int dp[1 + nmax][1 + nmax];
int v[1 + nmax];

void compute(int from, int to){
  int mid = (from + to) / 2;

  if(from < to) {
    compute(from, mid);
    compute(mid + 1, to);
  }

  for(int i = mid - 1; from <= i; i--){
    if(dp[i][mid] == -1)
      dp[i][mid] = Secret(v[i], dp[i + 1][mid]);
  }
  for(int i = mid + 2; i <= to; i++)
    if(dp[mid + 1][i] == -1)
      dp[mid + 1][i] = Secret(dp[mid + 1][i - 1], v[i]);
}
int n;

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

  for(int i = 0;i < N; i++)
    for(int j = i; j < N; j++)
      dp[i][j] = -1;
  for(int i = 0; i < n; i++)
    dp[i][i] = v[i];
  compute(0, N - 1);
}

int ask(int from, int to, int x, int y){
  int mid = (from + to)/ 2;
  if(-1 < dp[x][y])
    return dp[x][y];

  if(x <= mid && mid + 1 <= y)
    return Secret(dp[x][mid], dp[mid + 1][y]);
  else {
    if(y <= mid)
      return ask(from, mid, x, y);
    else
      return ask(mid + 1, to, x, y);
  }
}

int Query(int L, int R) {
  return ask(0, n - 1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 4472 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 172 ms 4604 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 172 ms 4460 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 606 ms 8408 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 597 ms 8320 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 597 ms 8456 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 604 ms 8440 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 607 ms 8520 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 601 ms 8316 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 603 ms 8272 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1