Submission #1280902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280902		SSKMF	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	26 ms	2716 KiB

apple

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

struct Nod {
    int activ = 0;
    Nod *stanga = NULL , *dreapta = NULL;
} *radacina;

inline int Query (Nod* &nod , const int stanga , const int dreapta , const int stanga_query , const int dreapta_query)
{
    if (nod == NULL || stanga_query > dreapta_query)
        { return 0; }

    if (nod -> activ == dreapta - stanga + 1)
        { return dreapta_query - stanga_query + 1; }

    const int mijloc = (stanga + dreapta) >> 1;
    return Query(nod -> stanga , stanga , mijloc , stanga_query , min(mijloc , dreapta_query)) + Query(nod -> dreapta , mijloc + 1 , dreapta , max(mijloc + 1 , stanga_query) , dreapta_query);
}

inline void Update (Nod* &nod , const int stanga , const int dreapta , const int stanga_update , const int dreapta_update)
{
    if (stanga_update > dreapta_update || (nod != NULL && nod -> activ == dreapta - stanga + 1))
        { return; }
    
    if (nod == NULL)
        { nod = new Nod; }

    if (stanga_update == stanga && dreapta == dreapta_update)
        { nod -> activ = dreapta - stanga + 1; return; }

    const int mijloc = (stanga + dreapta) >> 1;
    Update(nod -> stanga , stanga , mijloc , stanga_update , min(mijloc , dreapta_update));
    Update(nod -> dreapta , mijloc + 1 , dreapta , max(mijloc + 1 , stanga_update) , dreapta_update);
    nod -> activ = (nod -> stanga ? nod -> stanga -> activ : 0) + (nod -> dreapta ? nod -> dreapta -> activ : 0);
}

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

    int numar_operatii;
    cin >> numar_operatii;

    int rezultat = 0;
    while (numar_operatii--)
    {
        int tip , stanga , dreapta;
        cin >> tip >> stanga >> dreapta;

        stanga += rezultat;
        dreapta += rezultat;

        if (tip == 1)
            { cout << (rezultat = Query(radacina , 1 , 1000000000 , stanga , dreapta)) << '\n'; }
        else
            { Update(radacina , 1 , 1000000000 , stanga , dreapta); }
    }
    
    return 0;
}

• Subtask 1: 100 / 100