Submission #953696

#	Time	Username	Problem	Language	Result	Execution time	Memory
953696		infrapolar	Secret (JOI14_secret)	C++17	100 / 100	383 ms	4500 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
struct sparse_table
{
    vector<int> data[10];
    sparse_table(){}
    sparse_table(int sz, int* arr){
        data[0] = vector(arr, arr+sz);
        int block_size = 2;
        int j = 1;
        while (block_size < sz){
            data[j].assign(sz, 0);
            for (int begin = 0; begin < sz; begin+=2*block_size)
            {
                int center = min(sz-1, begin+block_size-1);
                data[j][center] = arr[center];
                for (int i = center - 1; i >= begin; i--)
                {
                    data[j][i] = Secret(arr[i], data[j][i+1]);
                }
                if (center != sz - 1)
                    data[j][center+1] = arr[center+1];
                for (int i = center+2; i < min(center+block_size+1, sz); i++)
                {
                    data[j][i] = Secret(data[j][i-1], arr[i]);
                }
                
            }
            block_size *= 2;
            j++;
        }
    }
    int query(int l, int r){
        if (l == r)
            return data[0][l];
        int layer = -1;
        int t = l ^ r;
        while (t){
            layer++;
            t >>= 1;
        }
        return Secret(data[layer][l], data[layer][r]);
    }
};
sparse_table str;
void Init(int N, int A[]) {
    str = sparse_table(N, A);
}

int Query(int L, int R) {
    return str.query(L, R);
}

• Subtask 1: 100 / 100