#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |