oj.uz

Submission #554591

# Submission time Handle Problem Language Result Execution time Memory
554591 2022-04-28T20:42:58 Z status_coding Secret (JOI14_secret) C++14
100 / 100
 451 ms 4412 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;

int a[1005];
int dp[10][1005];

void calc(int st, int dr, int p)
{
    if(st >= dr)
        return;

    int mij = (st + dr)/2;
    //cout<<st<<' '<<dr<<' '<<mij<<'\n';

    dp[p][mij-1] = a[mij-1];
    for(int i=mij-2; i>=st; i--)
        dp[p][i] = Secret(a[i], dp[p][i+1]);

    dp[p][mij] = a[mij];
    for(int i=mij+1; i<=dr; i++)
        dp[p][i] = Secret(dp[p][i-1], a[i]);

    calc(st, mij-1, p+1);
    calc(mij+1, dr, p+1);
}

int query(int stt, int drt, int st, int dr, int p)
{
    int mij = (st+dr)/2;

    if(drt < mij)
        return query(stt, drt, st, mij-1, p+1);
    if(stt > mij)
        return query(stt, drt, mij+1, dr, p+1);

    if(stt == mij)
        return dp[p][drt];
    else
        return Secret(dp[p][stt], dp[p][drt]);
}

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

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

    //cout<<"build\n";
    calc(0, n-1, 1);

    /*
    cout<<"debug\n";

    for(int i=0;i<n;i++)
        cout<<dp[1][i]<<' ';
    cout<<"\n\n";
    */
}

int Query(int l, int r)
{
    if(l == r)
        return a[l];

    return query(l, r, 0, n-1, 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2392 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 126 ms 2356 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 127 ms 2380 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 438 ms 4328 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 441 ms 4308 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 439 ms 4312 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 435 ms 4324 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 448 ms 4388 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 434 ms 4400 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 451 ms 4412 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1