oj.uz

Submission #162022

# Submission time Handle Problem Language Result Execution time Memory
162022 2019-11-05T21:27:06 Z Alexa2001 Secret (JOI14_secret) C++17
100 / 100
 620 ms 8824 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1105;

int n;
int res[Nmax][Nmax], A[Nmax];

void divide(int st, int dr)
{
    if(dr - st <= 1) return;

    int mid = (st + dr) / 2;

    divide(st, mid);
    divide(mid+1, dr);

    int i;
    for(i=mid-1; i>=st; --i)
        if(res[i][mid] == -1)
            res[i][mid] = Secret(A[i], res[i+1][mid]);

    for(i=mid+2; i<=dr; ++i)
        if(res[mid+1][i] == -1)
            res[mid+1][i] = Secret(res[mid+1][i-1], A[i]);
}

void Init(int N, int _A[])
{
    n = N;

    int i, j;
    for(i=0; i<n; ++i) A[i] = _A[i];

    for(i=0; i<n; ++i)
        for(j=i; j<n; ++j)
            res[i][j] = -1;

    for(i=0; i<n; ++i) res[i][i] = A[i];

    divide(0, n-1);
}

int answer(int st, int dr, int L, int R)
{
    int mid = (st + dr) / 2;

    if(L <= mid && mid + 1 <= R)
        return Secret(res[L][mid], res[mid+1][R]);

    if(R <= mid) return answer(st, mid, L, R);
        else return answer(mid+1, dr, L, R);
}

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

    /// lungime minim 3
    return answer(0, n-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 4756 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 173 ms 4600 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 174 ms 4624 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 603 ms 8584 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 600 ms 8740 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 620 ms 8648 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 617 ms 8824 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 602 ms 8700 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 605 ms 8712 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 603 ms 8716 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1