Submission #506093

#	Time	Username	Problem	Language	Result	Execution time	Memory
506093		MasterTaster	Global Warming (CEOI18_glo)	C++14	100 / 100	73 ms	4972 KiB

glo

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 200010
#define endl "\n"

using namespace std;

int n, x, a[MAXN], b[MAXN], dp[MAXN], lvd[MAXN], ress=-1; ///lvd=lis veci desno

int binarna(int cnt, int k)
{
    int l=0, r=cnt-1;
    int ret=-1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (dp[mid]<k)
        {
            ret=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ret;
}
int prviveci(int cnt, int k)
{
    int l=0, r=cnt-1;
    int ret=-1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (dp[mid]>k)
        {
            ret=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return ret;
}

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

    cin>>n>>x;
    int maxx=-1;
    for (int i=0; i<n; i++) { cin>>a[i]; maxx=max(maxx, a[i]); }

    for (int i=0; i<n; i++) b[i]=maxx-a[i];

    dp[0]=b[n-1];
    int cnt=1;
    lvd[n-1]=0; lvd[n-2]=0;
    if (a[n-1]>(a[n-2]-x)) lvd[n-2]=1;
    for (int i=n-2; i>/*=*/0; i--)
    {
        if (b[i]<dp[0]) dp[0]=b[i];
        else if (b[i]>dp[cnt-1]) dp[cnt++]=b[i];
        else
        {
            auto gde=prviveci(cnt, b[i]);
            if (gde==0 || dp[gde-1]!=b[i])
            {
                auto gde=prviveci(cnt, b[i]);
                dp[gde]=b[i];
            }
        }
        int kolko=a[i-1]-x;
        //cout<<i-1<<" "<<maxx-kolko<<" "<<cnt<<endl;
        lvd[i-1]=binarna(cnt, maxx-kolko)+1;
    }

    //for (int i=0; i<n; i++) cout<<lvd[i]<<" ";
    //cout<<endl;

    a[0]-=x;
    dp[0]=a[0];
    ress=max(ress, lvd[0]+1);
    cnt=1;
    for (int i=1; i<n; i++)
    {
        a[i]-=x;
        if (a[i]<dp[0]) dp[0]=a[i];
        else if (a[i]>dp[cnt-1]) dp[cnt++]=a[i];
        else
        {
            auto gde=prviveci(cnt, a[i]);
            if (gde==0 || dp[gde-1]!=a[i])
            {
                auto gde=prviveci(cnt, a[i]);
                dp[gde]=a[i];
            }
        }
        int kolko=binarna(cnt, a[i]);
        kolko++;
        ress=max(ress, (kolko+lvd[i]+1));
    }
    ress=max(ress, cnt);
    cout<<ress;

}
/*
15
20
1 7 3 20 8 3 17 10 3 27 14 17 13 9 15

5
10
1 4 2 7 10

5
1
1 4 2 7 10
*/

• 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