제출 #1175829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175829		redstonegamer22	비밀 (JOI14_secret)	C++20	30 / 100	356 ms	5308 KiB

secret

#include "secret.h"

#include <vector>
#include <map>
#include <utility>
#include <algorithm>

std::map<std::pair<int, int>, int> secret_map;
int mySecret(int X, int Y) {
    if(X == -2) return Y;
    if(Y == -2) return X;

    if(X == -1 || Y == -1) {
        return -1;
    }

    if(secret_map.find({X, Y}) != secret_map.end()) {
        return secret_map[{X, Y}];
    }

    return secret_map[{X, Y}] = Secret(X, Y);
}

struct SegTree {
    int offset;
    std::vector<int> tree;

    SegTree(int n, int a[]) {
        offset = 1;
        while (offset <= n) {
            offset *= 2;
        }
        tree.resize(2 * offset, -1);
        
        for(int i = 0; i < n; i++) {
            tree[offset + i] = a[i];
        }

        for(int i = offset - 1; i >= 1; i--) {
            tree[i] = mySecret(tree[2 * i], tree[2 * i + 1]);
        }
    }


    int _query(int node, int l, int r, int gl, int gr) {
        if (gl > r || gr < l) {
            return -2;
        }
        if (gl <= l && gr >= r) {
            return tree[node];
        }
        int mid = (l + r) / 2;
        return mySecret(_query(node * 2, l, mid, gl, gr), _query(node * 2 + 1, mid + 1, r, gl, gr));
    }

    int query(int l, int r) {
        return _query(1, 0, offset - 1, l, r);
    }
} st(0, nullptr);

void Init(int N, int A[]) {
    // int *ptr = new int[N];
    // ptr[i] <=> *(ptr + i);
    // i[ptr] = ptr[i] daca i = int, ptr = int*
    // ptr[i] = *(ptr + i) = *(i + ptr) = i[ptr]
    
    st = SegTree(N, A);
}

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

• Subtask 1: 30 / 100