Submission #1292484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292484		AliMark71	비밀 (JOI14_secret)	C++20	100 / 100	343 ms	4460 KiB

secret

//
//  dncRQ.hpp
//  EliteCamp 2025
//
//  Created by Ali AlSalman on 19/11/2025.
//

#include <bits/stdc++.h>

template<typename T>
using vec = std::vector<T>;
using namespace std;

int Secret(int x, int y);

struct dncRQ {
    int n;
    vec<vec<int>> S;
    vec<int> M, A;
private:
    int _merge(int lhs, int rhs) {
        return Secret(lhs, rhs);
    }
    void _init(int l, int r, int d = 0, int mask = 0) {
        if (l + 1 == r) {
            M[l] = mask;
            S[d][l] = A[l];
            return;
        }
        
        int mid = (l + r) / 2;
        S[d][mid - 1] = A[mid - 1];
        S[d][mid] = A[mid];
        for (int i = mid + 1; i < r; i++)
            S[d][i] = _merge(S[d][i - 1], A[i]);
        for (int i = mid - 2; l <= i; i--)
            S[d][i] = _merge(A[i], S[d][i + 1]);
            
        
        _init(l, mid, d + 1, mask|(1<<d));
        _init(mid, r, d + 1, mask|(0<<d));
    }
public:
    dncRQ(const vec<int> &arr) {
        A = arr;
        n = (int) arr.size();
        S.resize(33, vec<int>(n));
        M.resize(n);
        _init(0, (int) arr.size());
    }
    
    int query(int l, int r) {
        if (l == r)
            return A[l];
        int lm = M[l], rm = M[r];
        int d = __builtin_ctz(lm ^ rm);
        return _merge(S[d][l], S[d][r]);
    }
};

dncRQ *rq;

void Init(int n, int a[]) {
    vec<int> arr(a, a + n);
    rq = new dncRQ(arr);
}

int Query(int l, int r) {
    return rq->query(l, r);
}

• Subtask 1: 100 / 100