oj.uz

Submission #52323

# Submission time Handle Problem Language Result Execution time Memory
52323 2018-06-25T12:25:40 Z Costin Andrei Oncescu(#1295) Secret (JOI14_secret) C++11
100 / 100
 697 ms 5644 KB 
#include "secret.h"

int N, a[1009], dp[10][1009];

void init (int lev, int l, int r)
{
    if (l == r) return ;
    int mid = (l + r) >> 1;
    dp[lev][mid] = a[mid];
    for (int i=mid - 1; i>=l; i--)
        dp[lev][i] = Secret (a[i], dp[lev][i + 1]);
    dp[lev][mid + 1] = a[mid + 1];
    for (int i=mid + 2; i<=r; i++)
        dp[lev][i] = Secret (dp[lev][i - 1], a[i]);
    init (lev + 1, l, mid);
    init (lev + 1, mid + 1, r);
}

void Init (int nn, int aa[])
{
    N = nn;
    for (int i=0; i<N; i++)
        a[i + 1] = aa[i];
    init (0, 1, N);
}

int solve (int lev, int l, int r, int x, int y)
{
    if (x == y) return a[x];
    int mid = (l + r) >> 1;
    if (x <= mid && mid < y)
    {
        int ans = Secret (dp[lev][x], dp[lev][y]);
        return ans;
    }
    else
    if (y <= mid) return solve (lev + 1, l, mid, x, y);
    return solve (lev + 1, mid + 1, r, x, y);
}

int Query (int L, int R)
{
    L ++, R ++;
    return solve (0, 1, N, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 2424 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 173 ms 2748 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 180 ms 2944 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 634 ms 4828 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 649 ms 5008 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 697 ms 5060 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 645 ms 5252 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 635 ms 5356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 603 ms 5356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 662 ms 5644 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1