oj.uz

Submission #483304

# Submission time Handle Problem Language Result Execution time Memory
483304 2021-10-28T15:06:34 Z Alexandruabcde Secret (JOI14_secret) C++14
100 / 100
 464 ms 8312 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

typedef long long LL;
constexpr int NMAX = 1005;

int n;
int V[NMAX];
int ans[NMAX][NMAX];

void Precalculare (int Left, int Right) {
    if (Left >= Right) return;

    int mij = (Left + Right) / 2;
    ans[mij][mij] = V[mij];

    for (int i = mij-1; i >= Left; -- i )
        ans[i][mij] = Secret(V[i], ans[i+1][mij]);

    ans[mij+1][mij+1] = V[mij+1];
    for (int i = mij+2; i <= Right; ++ i )
        ans[mij+1][i] = Secret(ans[mij+1][i-1], V[i]);

    Precalculare(Left, mij);
    Precalculare(mij+1, Right);
}

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

    Precalculare(1, N);
}

int Answer (int st, int dr, int qa, int qb) {
    int mij = (st + dr) / 2;

    if (qa <= mij && mij < qb)
        return Secret(ans[qa][mij], ans[mij+1][qb]);

    if (qb <= mij)
        return Answer(st, mij, qa, qb);

    return Answer(mij+1, dr, qa, qb);
}

int Query(int L, int R) {
    if (L == R) return V[L+1];

    return Answer(1, n, L+1, R+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 4440 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 122 ms 4332 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 127 ms 4296 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 441 ms 8124 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 450 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 436 ms 8260 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 438 ms 8180 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 464 ms 8188 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 431 ms 8152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 455 ms 8148 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1