Submission #1202266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202266		SSKMF	Queue (CEOI06_queue)	C++20	100 / 100	177 ms	14540 KiB

queue

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

map < int , pair <int , int> > locatie;
pair <int , int> sir[200000] , invers[200000];
int gasit[200000];

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

    int lungime;
    cin >> lungime;

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        int nod[2];
        cin >> nod[0] >> nod[1];
        
        map < int , pair <int , int> > :: iterator candidat_1 = locatie.find(nod[0]);
        map < int , pair <int , int> > :: iterator candidat_2 = locatie.find(nod[1]);
        if (candidat_1 == locatie.end()) { candidat_1 = locatie.insert({nod[0] , {nod[0] - 1 , nod[0] + 1}}).first; }
        if (candidat_2 == locatie.end()) { candidat_2 = locatie.insert({nod[1] , {nod[1] - 1 , nod[1] + 1}}).first; }

        map < int , pair <int , int> > :: iterator suplimentar = locatie.find(candidat_1 -> second.first);
        if (suplimentar == locatie.end()) { suplimentar = locatie.insert({candidat_1 -> second.first , {candidat_1 -> second.first - 1 , nod[0]}}).first; }
        suplimentar -> second.second = candidat_1 -> second.second;
        
        suplimentar = locatie.find(candidat_1 -> second.second);
        if (suplimentar == locatie.end()) { suplimentar = locatie.insert({candidat_1 -> second.second , {nod[0] , candidat_1 -> second.second + 1}}).first; }
        suplimentar -> second.first = candidat_1 -> second.first;
        
        suplimentar = locatie.find(candidat_2 -> second.first);
        if (suplimentar == locatie.end()) { suplimentar = locatie.insert({candidat_2 -> second.first , {candidat_2 -> second.first - 1 , nod[1]}}).first; }
        suplimentar -> second.second = nod[0];

        candidat_2 -> second.first = nod[0];

        candidat_1 -> second.first = suplimentar -> first;
        candidat_1 -> second.second = nod[1];
    }

    for (auto& candidat : locatie)
        { gasit[++gasit[0]] = candidat.first; }

    int pozitie = 0 , termen = 0 , __valoare = 0;
    for (auto& candidat : locatie) {
        if (locatie.find(candidat.second.first) == locatie.end())
        {
            const int anterior = termen;
            for (int putere = (1 << 17) ; putere ; putere >>= 1) {
                if (termen + putere < gasit[0] && gasit[termen + putere] < candidat.first)
                    { termen += putere; }
            }

            pozitie += (candidat.first - __valoare) - (termen - anterior);
            __valoare = candidat.first;

            int nod = candidat.first;
            do {
                invers[++invers[0].first] = {nod , pozitie};
                sir[++sir[0].first] = {nod , pozitie++};
                nod = locatie.find(nod) -> second.second;
            } while (locatie.find(nod) != locatie.end());
        }
    }

    sort(invers + 1 , invers + invers[0].first + 1);

    int numar_intrebari;
    cin >> numar_intrebari;

    while (numar_intrebari--)
    {
        int8_t tip;
        cin >> tip >> __valoare;

        if (tip == 'P')
        {
            pozitie = 0;
            for (int putere = (1 << 17) ; putere ; putere >>= 1) {
                if ((pozitie | putere) <= invers[0].first && invers[pozitie | putere].first <= __valoare)
                    { pozitie |= putere; }
            }

            cout << __valoare - (pozitie == 0 ? 0 : invers[pozitie].first) + invers[pozitie].second << '\n';
        }
        else
        {
            pozitie = 0;
            for (int putere = (1 << 17) ; putere ; putere >>= 1) {
                if ((pozitie | putere) <= sir[0].first && sir[pozitie | putere].second <= __valoare)
                    { pozitie |= putere; }
            }

            cout << __valoare - sir[pozitie].second + (pozitie == 0 ? 0 : sir[pozitie].first) << '\n';
        }
    }
    
    return 0;
}

• Subtask 1: 100 / 100