Submission #1202372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202372		SSKMF	Balloons (CEOI11_bal)	C++20	100 / 100	349 ms	18256 KiB

bal

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

struct Functie {
    int termen; long double factor;
    Functie (const int __termen = 0 , const int __factor = 1e-18) : termen(__termen) , factor(__factor) { }
    ~Functie () { }
    long double operator ()(const int punct) {
        return punct < termen ? punct - termen : (long double)(punct - termen) * (punct - termen) / (4 * factor);
    }
};

Functie candidati[400000];
pair <int , int> sir[200001] , copie[200001];
int inlocuitor[200001];

inline void Insert (int nod , int stanga , int dreapta , Functie candidat)
{
    while (true)
    {
        const int mijloc = (stanga + dreapta) >> 1;
        const bool rezultat_1 = (candidati[nod](inlocuitor[stanga]) > candidat(inlocuitor[stanga]));
        const bool rezultat_2 = (candidati[nod](inlocuitor[mijloc]) > candidat(inlocuitor[mijloc]));
        if (rezultat_2) { swap(candidati[nod] , candidat); }
        if (stanga == dreapta) { break; }
        if (rezultat_1 != rezultat_2) { nod++; dreapta = mijloc; }
        else { nod += ((mijloc - stanga + 1) << 1); stanga = mijloc + 1; }
    }
}

inline long double Query (int nod , int stanga , int dreapta , const int indice)
{
    long double minim = 1e18;
    while (true)
    {
        minim = min(minim , candidati[nod](inlocuitor[indice]));
        if (stanga == dreapta) { break; }
        const int mijloc = (stanga + dreapta) >> 1;
        if (indice <= mijloc) { nod++; dreapta = mijloc; }
        else { nod += ((mijloc - stanga + 1) << 1); stanga = mijloc + 1; }
    }

    return minim;
}

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

    int lungime;
    cin >> lungime;

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

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

    int limita = 0;
    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        const int actual = copie[indice--].first;
        inlocuitor[++limita] = actual;

        while (indice < lungime && copie[indice + 1].first == actual)
            { sir[copie[++indice].second].first = limita; }
    }

    cout << fixed << setprecision(3);

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        Functie actual(sir[indice].first , sir[indice].second);
        actual.factor = min(actual.factor , Query(1 , 1 , limita , actual.termen));
        actual.termen = inlocuitor[actual.termen];
        Insert(1 , 1 , limita , actual);
        cout << actual.factor << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10