Submission #1292465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292465		AliMark71	비밀 (JOI14_secret)	C++20	0 / 100	343 ms	4456 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, mx_d;
    vec<vec<int>> S;
    vec<int> M;
private:
    int _merge(int lhs, int rhs) {
        return Secret(lhs, rhs);
    }
    void _init(int l, int r, vec<int> &a, int d = 0, int mask = 0) {
        if (l + 1 == r) {
            M[l] = mask;
            S[d][l] = a[l]; mx_d = d;
            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, a, d + 1, mask|(1<<d));
        _init(mid, r, a, d + 1, mask|(0<<d));
    }
public:
    dncRQ(vec<int> &arr) {
        n = (int) arr.size();
        S.resize(33, vec<int>(n));
        M.resize(n);
        _init(0, (int) arr.size(), arr);
    }
    
    int query(int l, int r) {
        if (l == r)
            return S[mx_d][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: 0 / 100