Submission #706500

#	Time	Username	Problem	Language	Result	Execution time	Memory
706500		VladPislaru	Global Warming (CEOI18_glo)	C++17	100 / 100	109 ms	5288 KiB

glo

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int n, x, nr;
int a[200005];
int dp[200005];
int dp2[200005];
int best[200005];
int best2[200005];
int ans;


void CB(int i)
{
    int st, dr, p, mij, val = a[i];
    if (val <= dp[1])
    {
        dp[1] = val;
        best[i] = 1;
        return;
    }

    if (val > dp[nr])
    {
        nr++;
        dp[nr] = val;
        best[i] = nr;
        return ;
    }

    /// caut cea mai din stanga poz. p cu a[i]<= dp[p]
    st = 1; dr = nr; p = nr;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (val <= dp[mij])
        {
            p = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    dp[p] = val;
    best[i] = p;
}

int Get_ans(int i) {
    int st, dr, mij, val = a[i] - x, p;
    if (val >= dp2[1])
        return 1;
    if (val < dp2[nr])
        return nr + 1;
    st = 1, dr = nr, p = nr;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (val >= dp2[mij]) {
            p = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return p;
}

void CB2 (int i) {
    int st, dr, mij, val = a[i], p;
    if (val >= dp2[1]) {
        dp2[1] = val;
        return;
    }
    else if (val < dp2[nr]) {
        nr++;
        dp2[nr] = val;
        return;
    }
    st = 1, dr = nr, p = nr;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (val >= dp2[mij]) {
            p = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    dp2[p] = val;
}
int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    best[1] = 1;
    dp[1] = a[1];
    dp[0] = 0;
    nr = 1;
    for (int i = 2; i <= n; i++) {
        CB(i);
    }
    ans = nr;
    best2[n] = 1;
    dp2[1] = a[n];
    nr = 1;

    for (int i = n - 1; i > 0; i--) {
        best2[i] = Get_ans(i);
        CB2(i);
        ////cout << best2[i] << "\n";
        ans = max(best[i] + best2[i] - 1, ans);
    }
    cout << ans << "\n";
    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