Submission #1305654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305654		kaloyan	Secret (JOI14_secret)	C++20	100 / 100	342 ms	4456 KiB

secret

#include "secret.h"
#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 1000;
const int MAXLOG = 10;

int n;
int a[MAXN];
int sparse[MAXN][MAXLOG];
int mask[MAXN];

void divide(int l, int r, int level)
{
    if(l == r)
    {
        sparse[l][level] = a[l];
        return;
    }

    int mid = (l + r) / 2;

    divide(l, mid, level + 1); 
    divide(mid + 1, r, level + 1);

    sparse[mid][level] = a[mid];
    for(int i = mid - 1 ; i >= l ; --i)
    {
        sparse[i][level] = Secret(a[i], sparse[i + 1][level]);
    }

    sparse[mid + 1][level] = a[mid + 1];
    for(int i = mid + 2 ; i <= r ; ++i)
    {
        sparse[i][level] = Secret(sparse[i - 1][level], a[i]);
    }

    for(int i = mid + 1 ; i <= r ; ++i)
    {
        mask[i] |= (1 << level);
    }
}

void Init(int size, int arr[])
{
    n = size;
    for(int i = 0 ; i < n ; ++i)
    {
        a[i] = arr[i];
    }

    divide(0, n - 1, 0);
}

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

    int level = __builtin_ctz(mask[l] ^ mask[r]);
    return Secret(sparse[l][level], sparse[r][level]);
}

• Subtask 1: 100 / 100