Submission #1222098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222098		Tenis0206	Global Warming (CEOI18_glo)	C++20	0 / 100	173 ms	5844 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

int n, x;
int v[nmax + 5];

int dp_st[nmax + 5], dp_dr[nmax + 5];

struct arbore_indexat_binar
{
    int aib[nmax + 5];

    int ub(int x)
    {
        return (x & (-x));
    }

    void update(int poz, int val)
    {
        for(int i=poz;i<=n;i+=ub(i))
        {
            aib[i] = max(aib[i], val);
        }
    }

    int query(int poz)
    {
        int rez = 0;
        for(int i=poz;i>=1;i-=ub(i))
        {
            rez = max(rez, aib[i]);
        }
        return rez;
    }
}aib_st, aib_dr, aib;

vector<int> a;

int get_val(int val)
{
    int st = 1;
    int dr = a.size();
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(a[mij - 1] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        a.push_back(v[i]);
    }
    sort(a.begin(), a.end());
    for(int i=1;i<=n;i++)
    {
        dp_st[i] = 1 + aib_st.query(get_val(v[i] - 1));
        aib_st.update(get_val(v[i]), dp_st[i]);
    }
    for(int i=n;i>=1;i--)
    {
        dp_dr[i] = 1 + aib_dr.query(get_val(v[i] - 1));
        aib_dr.update(get_val(v[i]), dp_dr[i]);
    }
    int rez = 1;
    for(int i=1;i<=n;i++)
    {
        rez = max(rez, dp_dr[i] + aib.query(get_val(v[i] + x - 1)));
        aib.update(get_val(v[i]), dp_st[i]);
    }
    cout<<rez<<'\n';
    return 0;
}

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