Submission #1138954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138954		SSKMF	Klasika (COCI20_klasika)	C++20	110 / 110	1624 ms	421764 KiB

klasika

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

struct Nod { Nod* stanga = NULL , *dreapta = NULL; set <int> valori; } *radacina;
struct Operatie { int8_t tip; pair <int , int> valoare; } operatii[200001];
int cantitate , urmatorul[200002] , capat[200002] , inceput[200002] , sfarsit[200002] , valoare[200002];

inline void Parcurgere (const int nod_actual)
{
    inceput[nod_actual] = ++inceput[0];
    for (int indice = capat[nod_actual] ; indice ; indice = urmatorul[indice])
        { Parcurgere(indice); }

    sfarsit[nod_actual] = inceput[0];
}

inline void Insert (Nod* &nod , const int valoare , const int locatie , const int putere)
{
    if (!nod)
        { nod = new Nod; }

    nod -> valori.insert(locatie);

    if (!putere)
        { return; }

    if (valoare & putere)
        { Insert(nod -> dreapta , valoare , locatie , putere >> 1); }
    else
        { Insert(nod -> stanga , valoare , locatie , putere >> 1); }
}

inline int Query (Nod* &nod , const int valoare , const int minim , const int maxim , const int putere)
{
    if (!putere)
        { return 0; }

    if (valoare & putere) 
    {
        if (nod -> stanga)
        {
            set <int> :: iterator locatie = nod -> stanga -> valori.lower_bound(minim);
            if (locatie != nod -> stanga -> valori.end() && *locatie <= maxim)
                { return Query(nod -> stanga , valoare , minim , maxim , putere >> 1) | putere; }
        }

        return Query(nod -> dreapta , valoare , minim , maxim , putere >> 1);
    }

    if (nod -> dreapta)
    {
        set <int> :: iterator locatie = nod -> dreapta -> valori.lower_bound(minim);
        if (locatie != nod -> dreapta -> valori.end() && *locatie <= maxim)
            { return Query(nod -> dreapta , valoare , minim , maxim , putere >> 1) | putere; }
    }

    return Query(nod -> stanga , valoare , minim , maxim , putere >> 1);
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_operatii;
    cin >> numar_operatii;

    int lungime = 1;
    for (int indice = 1 ; indice <= numar_operatii ; indice++)
    {
        char tip[8];
        cin >> tip >> operatii[indice].valoare.first >> operatii[indice].valoare.second;
        operatii[indice].tip = tip[0];
        
        if (operatii[indice].tip == 'A') 
        { 
            urmatorul[++lungime] = capat[operatii[indice].valoare.first]; 
            capat[operatii[indice].valoare.first] = lungime;
        }
    }

    Parcurgere(1);

    lungime = 1;
    Insert(radacina , 0 , 1 , (1 << 30));
    for (int indice = 1 ; indice <= numar_operatii ; indice++) {
        if (operatii[indice].tip == 'A')
        {
            lungime++;
            const int actual = (valoare[inceput[operatii[indice].valoare.first]] ^ operatii[indice].valoare.second);
            Insert(radacina , actual , inceput[lungime] , (1 << 30));
            valoare[inceput[lungime]] = actual;
        }
        else
            { cout << Query(radacina , valoare[inceput[operatii[indice].valoare.first]] , inceput[operatii[indice].valoare.second] , sfarsit[operatii[indice].valoare.second] , (1 << 30)) << '\n'; }
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44