제출 #1277903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277903		SSKMF	Bouquet (EGOI24_bouquet)	C++20	100 / 100	54 ms	3652 KiB

Main

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

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30