oj.uz

Submission #916431

# Submission time Handle Problem Language Result Execution time Memory
916431 2024-01-25T21:31:24 Z Dec0Dedd Secret (JOI14_secret) C++14
100 / 100
 388 ms 8564 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e3+10;

int n, a[N], que[N][N];

void gen(int l, int r) {
    if (l == r) {
        que[l][l]=a[l];
        return;
    } int m=(l+r)/2;
    gen(l, m), gen(m+1, r);

    que[m+1][m+1]=a[m+1];
    for (int i=m+2; i<=r; ++i) que[m+1][i]=Secret(que[m+1][i-1], a[i]);
    que[m][m]=a[m];
    for (int i=m-1; i>=l; --i) que[i][m]=Secret(a[i], que[i+1][m]);
}

void Init(int _n, int ax[]) {
    n=_n;
    for (int i=1; i<=n; ++i) a[i]=ax[i-1];
    gen(1, n);
}

int ans(int l, int r, int ql, int qr) {
    if (l == r) return que[l][l];
    int m=(l+r)/2;
    if (ql <= m && m+1 <= qr) return Secret(que[ql][m], que[m+1][qr]);
    if (qr <= m) return ans(l, m, ql, qr);
    return ans(m+1, r, ql, qr); 
}

int Query(int ql, int qr) {
    return ans(1, n, ql+1, qr+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6840 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 108 ms 6740 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 6820 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 379 ms 8372 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 383 ms 8528 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 380 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 383 ms 8356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 380 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 388 ms 8564 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 381 ms 8360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1