oj.uz

Submission #349938

# Submission time Handle Problem Language Result Execution time Memory
349938 2021-01-18T18:04:59 Z blue Secret (JOI14_secret) C++11
100 / 100
 532 ms 8420 KB 
#include "secret.h"
#include <iostream>
#include <vector>
using namespace std;



//midpoint, endpoint
int res[1000][1000];

int N;
vector<int> A(1000);

void precompute(int a, int b)
{
    if(a == b)
    {
        res[a][a] = A[a];
        return;
    }
    if(a+1 == b)
    {
        res[a][b] = A[b];
        res[a][a] = A[a];
        return;
    }

    int m = (a+b)/2;

    res[m][m+1] = A[m+1];
    for(int i = m+2; i <= b; i++) res[m][i] = Secret(res[m][i-1], A[i]);

    res[m][m] = A[m];
    for(int i = m-1; i >= a; i--) res[m][i] = Secret(A[i], res[m][i+1]);

    precompute(a, m);
    precompute(m+1, b);
}

void Init(int n, int a[])
{
    N = n;
    for(int i = 0; i < N; i++) A[i] = a[i];

    precompute(0, N-1);
}



int query1(int L, int R, int a, int b)
{
    int m = (a+b)/2;
    if(L <= m && m+1 <= R) return Secret(res[m][L], res[m][R]);
    else if(R <= m) return query1(L, R, a, m);
    else return query1(L, R, m+1, b);
}

int Query(int L, int R)
{
    if(L == R) return A[L];
    if(L+1 == R) return Secret(A[L], A[R]);
    return query1(L, R, 0, N-1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 4544 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 510 ms 8256 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 532 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 508 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 511 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 507 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 8420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1