Submission #795758

#	Time	Username	Problem	Language	Result	Execution time	Memory
795758		Arshi	Global Warming (CEOI18_glo)	C++17	100 / 100	54 ms	5388 KiB

glo

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb(x)               push_back(x)
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)

const ll INF = 2e9 + 8;
const ll MOD = 1e9 + 7;
const ll MXN = 2e5 + 6;
const ll LOG = 28 - 5;

int  n , k , mx , ans;

int A[MXN] , B[MXN];
int dp[MXN] , pd[MXN];

void lis()
{
    fill(pd , pd + MXN , INF);
    pd[0] = 0;
    for(int i = 1 ; i <= n ; i ++) {
        int j = lower_bound(pd , pd + MXN , B[i]) - pd;
        dp[n + 1 - i] = j;
        pd[j] = min(pd[j] , B[i]);
    }
}

void sil()
{
    fill(pd , pd + MXN , INF);
    pd[0] = 0;
    for(int i = 1 ; i <= n ; i ++) {
        int j = lower_bound(pd , pd + MXN , A[i] + k) - pd;
        ans = max(ans , j + dp[i] - 1);
        j = lower_bound(pd , pd + MXN , A[i]) - pd;
        pd[j] = min(pd[j] , A[i]);
    }
}

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

    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> A[i];
        mx = max(A[i] , mx);
    }
    for(int i = 1 ; i <= n ; i ++)
        B[i] = (- A[n + 1 - i]) + mx + 1;

    lis();
    sil();

    cout << ans << '\n';

    return 0;
}

/*!
ahkh
*/

• 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