Submission #1280437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280437		SSKMF	Secret (JOI14_secret)	C++20	100 / 100	344 ms	4668 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector <int> rezultat[2000][2];
int limita , sir[1001];

inline void Build (const int nod , const int stanga , const int dreapta , const int tip)
{
    if (stanga == dreapta)
    {
        rezultat[nod][0].push_back(sir[stanga]);
        rezultat[nod][1].push_back(sir[stanga]);
        return;
    }

    const int mijloc = (stanga + dreapta) >> 1;

    Build(nod + 1 , stanga , mijloc , 1 | ((tip & 2) ? 2 : 0));
    Build(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , ((tip & 1) ? 1 : 0) | 2);

    if (tip & 1)
    {
        for (int indice = stanga ; indice <= mijloc ; indice++)
            { rezultat[nod][0].push_back(Secret(rezultat[nod + 1][0][indice - stanga] , rezultat[nod + ((mijloc - stanga + 1) << 1)][0][0])); }

        for (int indice = mijloc + 1 ; indice <= dreapta ; indice++)
            { rezultat[nod][0].push_back(rezultat[nod + ((mijloc - stanga + 1) << 1)][0][indice - (mijloc + 1)]); }
    }

    if (tip & 2)
    {
        for (int indice = stanga ; indice <= mijloc ; indice++)
            { rezultat[nod][1].push_back(rezultat[nod + 1][1][indice - stanga]); }

        for (int indice = mijloc + 1 ; indice <= dreapta ; indice++)
            { rezultat[nod][1].push_back(Secret(rezultat[nod + 1][0][0] , rezultat[nod + ((mijloc - stanga + 1) << 1)][1][indice - (mijloc + 1)])); }
    }
}

int Query (int stanga , int dreapta)
{
    int nod = 1 , __stanga = 0 , __dreapta = limita - 1;
    while (__stanga != __dreapta)
    {
        const int mijloc = (__stanga + __dreapta) >> 1;
        if (dreapta <= mijloc) { nod++; __dreapta = mijloc; }
        else if (stanga > mijloc) { nod += ((mijloc - __stanga + 1) << 1); __stanga = mijloc + 1; }
        else { break; }
    }

    if (__stanga == __dreapta) 
        { return rezultat[nod][0][0]; }

    const int mijloc = (__stanga + __dreapta) >> 1;
    return Secret(rezultat[nod + 1][0][stanga - __stanga] , rezultat[nod + ((mijloc - __stanga + 1) << 1)][1][dreapta - (mijloc + 1)]);
}

void Init (int lungime , int __sir[])
{
    limita = lungime;
    for (int indice = 0 ; indice < limita ; indice++)
        { sir[indice] = __sir[indice]; }

    Build(1 , 0 , lungime - 1 , 0);
}

• Subtask 1: 100 / 100