Submission #1326629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326629		SSKMF	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	600 ms	56364 KiB

sortbooks

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

int sir[1000001] , stiva[1000001] , maxim[1000001];
vector < pair < pair <int , int> , int > > intrebari[1000001];
char rezultat[1000001];

inline void Update (int indice , const int valoare)
{
    for ( ; indice ; indice ^= (indice & -indice))
        { maxim[indice] = max(maxim[indice] , valoare); }
}

inline int Query (int indice , const int limita)
{
    int __maxim = 0;
    for ( ; indice <= limita ; indice += (indice & -indice))
        { __maxim = max(__maxim , maxim[indice]); }

    return __maxim;
}

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]; }

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
    {
        int stanga , dreapta , limita;
        cin >> stanga >> dreapta >> limita;
        intrebari[dreapta].emplace_back(make_pair(stanga , limita) , indice);
    }

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        while (stiva[0] && sir[indice] >= sir[stiva[stiva[0]]])
            { stiva[0]--; }

        if (stiva[0])
            { Update(stiva[stiva[0]] , sir[stiva[stiva[0]]] + sir[indice]); }
        
        stiva[++stiva[0]] = indice;

        for (auto& intrebare : intrebari[indice])
            { rezultat[intrebare.second] = (Query(intrebare.first.first , indice) <= intrebare.first.second ? '1' : '0'); }
    }

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

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23