oj.uz

Submission #68562

# Submission time Handle Problem Language Result Execution time Memory
68562 2018-08-17T10:36:30 Z evpipis Secret (JOI14_secret) C++11
100 / 100
 673 ms 12608 KB 
#include <bits/stdc++.h>
#include "secret.h"

//#define TEST

#ifdef TEST
#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];

static int secret_count;

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;
}
#endif

const int len = 1005;
int arr[len], val[4*len][len], n;

void build(int p, int l, int r){
    int mid = (l+r)/2;
    val[p][mid] = arr[mid];
    if (l != r) val[p][mid+1] = arr[mid+1];
    for (int i = mid-1; i >= l; i--)
        val[p][i] = Secret(arr[i], val[p][i+1]);
    for (int i = mid+2; i <= r; i++)
        val[p][i] = Secret(val[p][i-1], arr[i]);

    if (l != r)
        build(2*p, l, mid), build(2*p+1, mid+1, r);
}

int query(int p, int l, int r, int i, int j){
    if (l == r)
        return arr[l];

    int mid = (l+r)/2;
    if (j <= mid)
        return query(2*p, l, mid, i, j);
    else if (i > mid)
        return query(2*p+1, mid+1, r, i, j);
    return Secret(val[p][i], val[p][j]);
}

void Init(int N, int A[]) {
    n = N;
    for (int i = 0; i < n; i++)
        arr[i] = A[i];
    build(1, 0, n-1);

    Secret(0, 1000000000);
}

int Query(int l, int r) {
    return query(1, 0, n-1, l, r);
}

#ifdef TEST
int main() {
  freopen("input.txt", "r", stdin);
  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;
    printf("%d\n", Query(L[j], R[j]));
    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;
}
#endif

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6392 KB Output is correct - number of calls to Secret by Init = 3579, maximum number of calls to Secret by Query = 1
2 Correct 185 ms 6480 KB Output is correct - number of calls to Secret by Init = 3587, maximum number of calls to Secret by Query = 1
3 Correct 202 ms 6720 KB Output is correct - number of calls to Secret by Init = 3596, maximum number of calls to Secret by Query = 1
4 Correct 673 ms 12256 KB Output is correct - number of calls to Secret by Init = 7970, maximum number of calls to Secret by Query = 1
5 Correct 640 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
6 Correct 641 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
7 Correct 613 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
8 Correct 651 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
9 Correct 635 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
10 Correct 634 ms 12608 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1