Submission #554474

#	Time	Username	Problem	Language	Result	Execution time	Memory
554474		status_coding	Global Warming (CEOI18_glo)	C++14	100 / 100	65 ms	11216 KiB

glo

#include <bits/stdc++.h>

using namespace std;

struct change
{
    long long p, lval;

    change(long long p, long long lval)
    {
        this->p = p;
        this->lval = lval;
    }
};

long long n,k,ans;
long long a[200005];

long long dpl[200005];

long long dpr[200005];
vector<change> changes;

void init()
{
    ans = 0;

    dpl[0] = -1e18;
    for(int i=1;i<=n;i++)
        dpl[i] = 1e18;

    dpr[0] = 1e18;
    for(int i=1;i<=n;i++)
        dpr[i] = -1e18;
}

void addR(long long x)
{
    long long st=1, dr=n, mij, last=1;
    while(st <= dr)
    {
        mij = (st + dr)/2;

        if(dpr[mij] <= x)
        {
            last = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }

    long long p = last;

    changes.push_back(change(p, dpr[p]));
    dpr[p] = x;
}

void delR()
{
    long long p = changes.back().p;
    long long lval = changes.back().lval;
    changes.pop_back();

    dpr[p] = lval;
}

long long queryR(long long x)
{
    long long st=0, dr=n, mij, last=0;
    while(st <= dr)
    {
        mij = (st+dr)/2;

        if(dpr[mij] > x)
        {
            last = mij;
            st = mij+1;
        }
        else
            dr = mij-1;
    }

    return last;
}

void addL(long long x)
{
    long long st=1, dr=n, mij, last=1;
    while(st <= dr)
    {
        mij = (st+dr)/2;

        if(dpl[mij] >= x)
        {
            last = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }

    long long p = last;

    //cout<<p<<' '<<queryR(x-k)<<"\n\n";

    dpl[p] = x;
    ans = max(ans, (long long)p + queryR(x-k));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    init();

    for(int i=n;i>=1;i--)
    {
        addR(a[i]);

        /*
        cout<<"at pos "<<i<<'\n';
        for(int j=0; j<=n; j++)
        {
            if(dpr[j] == 0)
                break;

            cout<<dpr[j]<<' ';
        }
        cout<<"\n\n";
        */
    }

    for(int i=1;i<=n;i++)
    {
        //cout<<"at pos "<<i<<'\n';

        delR();
        addL(a[i]);

        /*
        cout<<"left is\n";
        for(int j=0;j<=n;j++)
        {
            if(dpl[j] == 1e18)
                break;

            cout<<dpl[j]<<' ';
        }
        cout<<"\n\n";


        cout<<"right is\n";
        for(int j=0;j<=n;j++)
        {
            if(dpr[j] == -1e18)
                break;

            cout<<dpr[j]<<' ';
        }
        cout<<"\n\n";
        */
    }

    cout<<ans;
    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