Submission #1326740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326740		SSKMF	Global Warming (CEOI18_glo)	C++20	100 / 100	72 ms	2252 KiB

glo

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

int sir[200001] , stiva[200001] , termen[200001] , maxim;

inline void GetMax (const int lungime , const int limita)
{
    for (int indice = lungime ; indice ; indice--)
    {
        int stanga = 1 , dreapta = stiva[0];
        while (stanga <= dreapta)
        {
            const int mijloc = (stanga + dreapta) >> 1;
            if (stiva[mijloc] > sir[indice]) { stanga = mijloc + 1; }
            else { dreapta = mijloc - 1; }
        }

        if (stanga > stiva[0])
            { stiva[0]++; }

        stiva[stanga] = sir[indice];
        termen[indice] = stanga;
    }

    stiva[0] = 0;
    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        int stanga = 1 , dreapta = stiva[0];
        while (stanga <= dreapta)
        {
            const int mijloc = (stanga + dreapta) >> 1;
            if (stiva[mijloc] <= sir[indice] + limita) { stanga = mijloc + 1; }
            else { dreapta = mijloc - 1; }
        }

        maxim = max(maxim , dreapta + termen[indice]);
        
        stanga = 1 , dreapta = stiva[0];
        while (stanga <= dreapta)
        {
            const int mijloc = (stanga + dreapta) >> 1;
            if (stiva[mijloc] < sir[indice]) { stanga = mijloc + 1; }
            else { dreapta = mijloc - 1; }
        }

        if (stanga > stiva[0])
            { stiva[0]++; }

        stiva[stanga] = sir[indice];
    }

    stiva[0] = 0;
}

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

    int lungime , limita;
    cin >> lungime >> limita;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; }

    limita--;

    GetMax(lungime , limita);

    for (int stanga = 1 , dreapta = lungime ; stanga < dreapta ; stanga++ , dreapta--)
    {
        swap(sir[stanga] , sir[dreapta]);
        sir[dreapta] *= -1;
        sir[stanga] *= -1;
    }

    if (lungime & 1)
        { sir[(lungime + 1) >> 1] *= -1; }

    GetMax(lungime , limita);

    cout << maxim;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25