Submission #1280025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280025		SSKMF	Examination (JOI19_examination)	C++20	100 / 100	1211 ms	89320 KiB

examination

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

mt19937_64 generator(72837923749);//(chrono::steady_clock::now().time_since_epoch().count());
struct Nod { uint64_t prioritate = generator(); int cantitate = 0 , valoare = 0; Nod *stanga = NULL , *dreapta = NULL; } *arbore[200000];
struct Intrebare { int limita_1 , limita_2 , limita_3 , indice; } intrebare[100001];
pair <int , int> sir[100001] , copie[100001];
int rezultat[100001] , temporar[100001];

inline int __size (Nod* &nod) { return nod ? nod -> cantitate : 0; }

inline void RotateLeft (Nod* &nod)
{
    Nod *inlocuitor = nod -> stanga;
    nod -> stanga = inlocuitor -> dreapta;
    inlocuitor -> dreapta = nod;
    
    nod -> cantitate = 1 + __size(nod -> stanga) + __size(nod -> dreapta);
    nod = inlocuitor;
    nod -> cantitate = 1 + __size(nod -> stanga) + __size(nod -> dreapta);
}

inline void RotateRight (Nod* &nod)
{
    Nod *inlocuitor = nod -> dreapta;
    nod -> dreapta = inlocuitor -> stanga;
    inlocuitor -> stanga = nod;
    
    nod -> cantitate = 1 + __size(nod -> stanga) + __size(nod -> dreapta);
    nod = inlocuitor;
    nod -> cantitate = 1 + __size(nod -> stanga) + __size(nod -> dreapta);
}

inline void Insert (Nod* &nod , const int valoare)
{
    if (nod == NULL)
    {
        nod = new Nod();
        nod -> valoare = valoare;
        nod -> cantitate = 1;
        return;
    }

    nod -> cantitate++;
    if (valoare < nod -> valoare) {
        Insert(nod -> stanga , valoare);
        if (nod -> stanga -> prioritate > nod -> prioritate)
            { RotateLeft(nod); }
    } else {
        Insert(nod -> dreapta , valoare);
        if (nod -> dreapta -> prioritate > nod -> prioritate)
            { RotateRight(nod); }
    }
}

inline int Query (Nod* &nod , const int valoare)
{
    if (nod == NULL)
        { return 0; }

    if (nod -> valoare < valoare)
        { return Query(nod -> dreapta , valoare); }

    return 1 + __size(nod -> dreapta) + Query(nod -> stanga , valoare);
}

inline void Update (const int nod , const int stanga , const int dreapta , const int indice , const int valoare)
{
    Insert(arbore[nod] , valoare);
    if (stanga == dreapta)
        { return; }

    const int mijloc = (stanga + dreapta) >> 1;
    if (indice <= mijloc) { Update(nod + 1 , stanga , mijloc , indice , valoare); }
    else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice , valoare); }
}

inline int Query (const int nod , const int stanga , const int dreapta , const int indice , const int valoare)
{
    if (dreapta < indice)
        { return 0; }

    if (stanga >= indice)
        { return Query(arbore[nod] , valoare); }

    const int mijloc = (stanga + dreapta) >> 1;
    return Query(nod + 1 , stanga , mijloc , indice , valoare) + Query(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice , valoare);
}

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

    int lungime , numar_intrebari;
    cin >> lungime >> numar_intrebari;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice].first >> sir[indice].second; }

    sort(sir + 1 , sir + lungime + 1 , [] (pair <int , int>& optiune_1 , pair <int , int>& optiune_2) -> bool {
        return optiune_1.first + optiune_1.second > optiune_2.first + optiune_2.second;
    });

    for (int indice = 1 ; indice <= lungime ; indice++)
        { copie[indice] = {sir[indice].first , indice}; }

    sort(copie + 1 , copie + lungime + 1);

    for (int indice = 1 ; indice <= lungime ; indice++)
        { sir[copie[indice].second].first = indice; }

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
        { cin >> intrebare[indice].limita_1 >> intrebare[indice].limita_2 >> intrebare[indice].limita_3; intrebare[indice].indice = indice; }

    sort(intrebare + 1 , intrebare + numar_intrebari + 1 , [] (Intrebare& optiune_1 , Intrebare& optiune_2) -> bool {
        return optiune_1.limita_3 > optiune_2.limita_3;
    });

    for (int indice = 1 , __indice = 1 ; indice <= numar_intrebari ; indice++)
    {
        while (__indice <= lungime && intrebare[indice].limita_3 <= copie[sir[__indice].first].first + sir[__indice].second)
            { Update(1 , 1 , lungime , sir[__indice].first , sir[__indice].second); __indice++; }

        int stanga = 1 , dreapta = lungime;
        while (stanga <= dreapta)
        {
            const int mijloc = (stanga + dreapta) >> 1;
            if (copie[mijloc].first >= intrebare[indice].limita_1) { dreapta = mijloc - 1; }
            else { stanga = mijloc + 1; }
        }
        
        rezultat[intrebare[indice].indice] = Query(1 , 1 , lungime , stanga , intrebare[indice].limita_2);
    }

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
        { cout << rezultat[indice] << '\n'; }

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57