Submission #1175879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175879		Rareshika	Secret (JOI14_secret)	C++20	100 / 100	582 ms	5760 KiB

secret

#include "secret.h"

#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1050;
int NIVEL_MAX;
/*******************************/
// INPUT / OUTPUT


/*******************************/
/// GLOBAL DECLARATIONS

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 Mij
{
    int pos, st, dr;
    vector <int> pref, suf;

    Mij(int _st, int _dr, vector <int> &a)
    {
        st = _st; dr = _dr;
        pref.resize((dr - st) / 2 + 1);
        suf.resize((dr - st) / 2 + 1);

        if (st == dr)
        {
            pos = st;
            pref[0] = suf[0] = a[st];
            return;
        }

        pos = (st + dr) / 2;
        pref[0] = a[pos];
        suf[0] = a[pos + 1];

        if (dr - st + 1 == 2)
        {
            return;    
        }
        
        for (int i = pos - 1 ; i >= st ; -- i)
        {
            pref[pos - i] = mySecret(a[i], pref[pos - i - 1]);
        }

        for (int i = pos + 2 ; i <= dr ; ++ i)
        {
            suf[i - pos - 1] = mySecret(suf[i - pos - 2], a[i]);
        }
    }

    inline bool raspunde(int q_st, int q_dr)
    {
        if (q_st == q_dr) return pos == q_st;
        else return (st <= q_st && q_st <= pos && pos + 1 <= q_dr && q_dr <= dr);
    }

    inline int get_raspuns(int q_st, int q_dr)
    {
        if (q_st == q_dr) return pref[0];
        return mySecret(pref[pos - q_st], suf[q_dr - pos - 1]);
    }
};

struct Nivel
{
    int lvl;
    vector <Mij> mijloace;

    Nivel(int _lvl, vector <int> &a)
    {
        lvl = _lvl;
        int len = (1 << (NIVEL_MAX - lvl));

        for (int care = 0 ; care < (1 << lvl) ; ++ care)
        {
            int st = care * len;
            int dr = st + len - 1;

            mijloace.push_back({st, dr, a});
        }
    }
};

struct Nebunie
{
    vector <Nivel> nivele;

    Nebunie() {}

    Nebunie(vector <int> &a)
    {
        for (int i = 0 ; i <= NIVEL_MAX ; ++ i)
            nivele.push_back({i, a});
    }

    int query(int st, int dr)
    {
        for (auto nivel: nivele)
        {
            for (auto mij: nivel.mijloace)
            {
                if (mij.raspunde(st, dr))
                {
                    return mij.get_raspuns(st, dr);
                }
            }
        }
        return -1;
    }
} nebun;

void Init(int N, int A[]) {
    NIVEL_MAX = ceil(log2(N));
    vector <int> my_a;
    my_a.resize((1 << NIVEL_MAX));
    for (int i = 0 ; i < N ; ++ i) my_a[i] = A[i];
    for (int i = N ; i < my_a.size() ; ++ i) my_a[i] = -2;

    nebun = Nebunie(my_a);
}

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

• Subtask 1: 100 / 100