Submission #1202266

#TimeUsernameProblemLanguageResultExecution timeMemory
1202266SSKMFQueue (CEOI06_queue)C++20
100 / 100
177 ms14540 KiB
#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 timeMemoryGrader output
Fetching results...