Submission #1265227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265227		MongHwa	Global Warming (CEOI18_glo)	C++20	100 / 100	39 ms	4432 KiB

glo

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
using namespace std;

int arr[200005], brr[200005];
int dp[200005], dp2[200005];

void lds(int n)
{
    vector<int> lds;
    for(int i = n-1; i >= 0; i--)
    {
        int k = lower_bound(lds.begin(), lds.end(), brr[i]) - lds.begin();
        if(k == (int)lds.size())
            lds.push_back(brr[i]);
        else
            lds[k] = brr[i];
        dp[i] = k+1;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    cin >> n >> x;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        brr[i] = -arr[i];
    }

    lds(n);
    int ans = 0; vector<int> lis;
    for(int i = 0; i < n; i++)
    {
        int k = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
        if(k == (int)lis.size())
        {
            ans = max(ans, k+dp[i]);
            lis.push_back(arr[i]);
        }
        else
        {
            int k2 = lower_bound(lis.begin(), lis.end(), arr[i]+x) - lis.begin();
            ans = max(ans, k2+dp[i]);
            lis[k] = arr[i];
        }

        dp2[i] = k;
    }

    lis.clear();
    for(int i = n-1; i >= 0; i--)
    {
        int k = lower_bound(lis.begin(), lis.end(), brr[i]) - lis.begin();
        if(k == (int)lis.size())
        {
            ans = max(ans, k+dp2[i]);
            lis.push_back(brr[i]);
        }
        else
        {
            int k2 = lower_bound(lis.begin(), lis.end(), brr[i]+x) - lis.begin();
            ans = max(ans, k2+dp2[i]);
            lis[k] = arr[i];
        }
    }

    cout << ans << '\n';
}

• 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