oj.uz

Submission #246295

# Submission time Handle Problem Language Result Execution time Memory
246295 2020-07-08T15:06:34 Z Coroian_David Secret (JOI14_secret) C++11
100 / 100
 532 ms 4600 KB 
#include <bits/stdc++.h>

#include "secret.h"

#define MAX_N 1000
#define MAX_LOG 10

using namespace std;

int v[MAX_N + 1];

int dp[MAX_LOG + 1][MAX_N + 1];

int mi[MAX_LOG + 1];
int Secret(int X, int Y);

void divide(int st, int dr, int niv)
{
    if(st >= dr)
        return;

      //  cout << " FACEM DIVITE " << st << " " << dr << " " << niv << "\n";

    if(st == dr - 1)
    {
        dp[niv][st] = v[st];
        dp[niv][dr] = v[dr];

        return;
    }

    int mid = (st + dr) >> 1;
    mi[niv] = mid;

    dp[niv][mid] = v[mid];
    for(int i = mid - 1; i >= st; i --)
    {
        dp[niv][i] = Secret(v[i], dp[niv][i + 1]);
       // cout << "la " << i << " este " << dp[niv][i] << " ";
    }

    dp[niv][mid + 1] = v[mid + 1];
    for(int i = mid + 2; i <= dr; i ++){
        dp[niv][i] = Secret(dp[niv][i - 1], v[i]);
       // cout << "la " << i << " este " << dp[niv][i] << " ";
    }

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

int n;

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

    divide(1, n, 0);
}

int getRez(int st, int dr, int a, int b, int niv)
{
    if(st == dr)
        return v[st];

    int mid = (st + dr) >> 1;

    //cout << " GETREZ " << st << " " << dr << " " << mid << " " << niv <<" \n";

    if(b <= mid)
        return getRez(st, mid, a, b, niv + 1);

    if(a > mid)
        return getRez(mid + 1, dr, a, b, niv + 1);

   // cout << " ESTE SECRET " << dp[niv][st] << " " << dp[niv][dr] << "\n";

    return Secret(dp[niv][a], dp[niv][b]);
}

int Query(int L, int R)
{
    return getRez(1, n, L + 1, R + 1, 0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2552 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 154 ms 2552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 147 ms 2552 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 509 ms 4472 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 4532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 514 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 512 ms 4476 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 509 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 508 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1