oj.uz

Submission #96052

# Submission time Handle Problem Language Result Execution time Memory
96052 2019-02-05T13:13:52 Z bogdan10bos Secret (JOI14_secret) C++14
100 / 100
 620 ms 6024 KB 
#include <bits/stdc++.h>

//#define DEBUG

#ifndef DEBUG
#include "secret.h"
#endif

#ifdef DEBUG
int Secret(int, int);
#endif

using namespace std;

namespace My
{
    int N, I;
    int v[1005];
    int id[1005][1005];
    vector<int> lft[10005], rgt[10005];

    void divide(int st, int dr)
    {
        if(st >= dr)    return;
        id[st][dr] = ++I;
        int mij = st + (dr - st) / 2;

        int val = v[mij];
        lft[I].push_back(val);
        for(int i = mij - 1; i >= st; i--)
        {
            val = Secret(v[i], val);
            lft[I].push_back(val);
        }
        val = v[mij + 1];
        rgt[I].push_back(val);
        for(int i = mij + 2; i <= dr; i++)
        {
            val = Secret(val, v[i]);
            rgt[I].push_back(val);
        }

        divide(st, mij - 1);
        divide(mij + 2, dr);
    }

    void init(int _N, int A[])
    {
        N = _N;
        I = 0;
        for(int i = 1; i <= N; i++) v[i] = A[i - 1];
        divide(1, N);
    }

    int query(int st, int dr, int sti, int dri)
    {
        int mij = st + (dr - st) / 2;

        int I = id[st][dr];

        if(sti == mij + 1)
            return rgt[I][dri - sti];

        if(dri == mij)
            return lft[I][dri - sti];

        if(sti <= mij && mij + 1 <= dri)
            return Secret(lft[I][mij - sti], rgt[I][dri - mij - 1]);

        if(dri < mij)
            return query(st, mij - 1, sti, dri);
        if(sti > mij + 1)
            return query(mij + 2, dr, sti, dri);
        return -1;
    }

    int query(int st, int dr)
    {
        st++; dr++;
        if(st == dr)    return v[st];
        return query(1, N, st, dr);
    }
}

void Init(int N, int A[]) {
  My::init(N, A);
}

int Query(int L, int R) {
  return My::query(L, R);
}

#ifdef DEBUG
namespace Grader
{
    #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;
    }

    int main() {
      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;
    }
}

int Secret(int x, int y)
{
    return Grader::Secret(x, y);
}

int main()
{
    freopen("1.in", "r", stdin);
    Grader::main();
}
#endif

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3576 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 141 ms 3448 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 141 ms 3448 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 489 ms 5964 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 489 ms 5948 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 495 ms 5924 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 620 ms 6024 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 492 ms 5880 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 493 ms 5852 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 492 ms 5928 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1