oj.uz

Submission #446743

# Submission time Handle Problem Language Result Execution time Memory
446743 2021-07-23T07:53:33 Z ak2006 Secret (JOI14_secret) C++14
100 / 100
 526 ms 12264 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
// #define MAX_N                  1000
// #define MAX_Q                 10000
// #define MAX_VALUE        1000000000

// static int N;
// static int A[MAX_N];
// static int Q;
// static int L[MAX_Q];
// static int R[MAX_Q];

using vi = vector<int>;
using vvi = vector<vi>;
//static int secret_count;
int n = 1005;
vvi lef(n,vi(n)),rig(n,vi(n));
vi a;

// int Secret(int X, int Y) {
//   ++secret_count;
//   if (!(0 <= X && X <= MAX_VALUE)) {
//     fprintf(stderr, "Wrong Answer [1]\n");
//     exit(0);
//   }
//   if (!(0 <= Y && Y <= MAX_VALUE)) {
//     fprintf(stderr, "Wrong Answer [1]\n");
//     exit(0);
//   }
//   return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
// }

void build(int l,int r)
{

  if (l == r){lef[l][l] = rig[l][l] = a[l];return;}
  if (l == r - 1){
    int mid = (l + r)/2;
    lef[mid][mid] = a[mid];
    rig[mid + 1][mid] = a[mid + 1];
    rig[mid + 2][mid] = Secret(rig[mid + 1][mid],a[mid + 2]);
    return;
  }
  
  int mid = (l + r)/2;
  
  lef[mid][mid] = a[mid];
  rig[mid + 1][mid] = a[mid + 1];
  
  for (int i = mid - 1;i>=l;i--)lef[i][mid] = Secret(a[i],lef[i + 1][mid]);

  for (int i = mid + 2;i<=r + 1;i++)rig[i][mid] = Secret(rig[i - 1][mid],a[i]);
  
  build(l,mid - 1);
  build(mid + 1,r);
}

void Init(int N, int A[]) {
  n = N;
  a.resize(n + 1);
  for (int i = 1;i<=N;i++)a[i] = A[i - 1];
  build(1,n);
}

int Query(int L, int R,int l,int r) {
  if (L == R)return a[L];
  if (L == R - 1)return Secret(a[L],a[L + 1]);

  int mid = (l + r)/2;

  if (L <= mid && mid + 1 <= R){

    return Secret(lef[L][mid],rig[R][mid]);
  }
  
  if (R <= mid)return Query(L,R,l,mid - 1);
  return Query(L,R,mid + 1,r);
}
int Query(int L,int R)
{
  return Query(L + 1,R + 1,1,n);
}
// int main() {
//   freopen("input.txt","r",stdin);
//   freopen("output.txt","w",stdout);
//   //cout<<Secret(Secret(1,4),Secret(7,2))<<endl;
//   int i, j;
//   int secret_count_by_init;
//   int max_secret_count_by_query = 0;

//   if (1 != scanf("%d", &N)) {
//     fprintf(stderr, "error: cannot read N.\n");
//     exit(1);
//   }
//   if (!(1 <= N && N <= MAX_N)) {
//     fprintf(stderr, "error: N is out of bounds.\n");
//     exit(1);
//   }
//   for (i = 0; i < N; ++i) {
//     if (1 != scanf("%d", &A[i])) {
//       fprintf(stderr, "error: cannot read A[%d].\n", i);
//       exit(1);
//     }
//     if (!(0 <= A[i] && A[i] <= MAX_VALUE)) {
//       fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//   }
//   if (1 != scanf("%d", &Q)) {
//     fprintf(stderr, "error: cannot read Q.\n");
//     exit(1);
//   }
//   if (!(0 <= Q && Q <= MAX_Q)) {
//     fprintf(stderr, "error: Q is out of bounds.\n");
//     exit(1);
//   }
//   for (j = 0; j < Q; ++j) {
//     if (2 != scanf("%d%d", &L[j], &R[j])) {
//       fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
//       exit(1);
//     }
//     if (!(0 <= L[j] && L[j] <= R[j] && R[j] <= N - 1)) {
//       fprintf(stderr,
//               "error: L[%d] and R[%d] do not satisfy the constraints.\n",
//               j, j);
//       exit(1);
//     }
//   }

//   secret_count = 0;
//   Init(N, A);
//   secret_count_by_init = secret_count;

//   for (j = 0; j < Q; ++j) {
//     secret_count = 0;
//     cout<<Query(L[j],R[j])<<endl;

//     if (max_secret_count_by_query < secret_count) {
//       max_secret_count_by_query = secret_count;
//     }
//   }

//   fprintf(stderr, "number of calls to Secret by Init : %d\n",
//           secret_count_by_init);
//   fprintf(stderr, "maximum number of calls to Secret by Query : %d\n",
//           max_secret_count_by_query);

//   return 0;
// }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 10292 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 10356 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
3 Correct 148 ms 10308 KB Output is correct - number of calls to Secret by Init = 3604, maximum number of calls to Secret by Query = 1
4 Correct 526 ms 12240 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
5 Correct 521 ms 12264 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
6 Correct 511 ms 12264 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
7 Correct 519 ms 12244 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
8 Correct 510 ms 12184 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
9 Correct 513 ms 12212 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
10 Correct 511 ms 12256 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1