Submission #1277903

#TimeUsernameProblemLanguageResultExecution timeMemory
1277903SSKMFBouquet (EGOI24_bouquet)C++20
100 / 100
54 ms3652 KiB
#include <bits/stdc++.h>
using namespace std;

priority_queue < pair < int , pair <int , int> > > ramas;
int maxim[200001];

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

    return __maxim;
}

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

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

    int lungime;
    cin >> lungime;

    int rezultat = 0;
    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        int stanga , dreapta;
        cin >> stanga >> dreapta;

        const int candidat = Query(max(0 , indice - stanga - 1)) + 1;
        ramas.push({-(indice + dreapta) , {candidat , indice}});
        while (!ramas.empty() && ramas.top().first == -indice)
        {
            Update(ramas.top().second.second , ramas.top().second.first , lungime);
            ramas.pop();
        }

        rezultat = max(rezultat , candidat);
    }

    cout << rezultat;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...