Submission #1153636

#TimeUsernameProblemLanguageResultExecution timeMemory
1153636MPGGlobal Warming (CEOI18_glo)C++20
100 / 100
39 ms6644 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("fenceplan.in", "r", stdin); freopen("fenceplan.out", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
ll const maxn = 2e5 + 110;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e9 + 7;//998244353; //1e9 + 9;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}



ll n, k, arr[maxn], ans[maxn];
vector <ll> dp, pd;

int main(){
sariE;// filE;

cin >> n >> k;
dp.resize(n + 10);
pd.resize(n + 10);
for (int i = 0; i < n + 10; i++){
    dp[i] = inf;
    pd[i] = inf;
}
for (int i = 0; i < n; i++){
    cin >> arr[i];
}

ll mx = 0;
for (int i = 0; i < n; i++){
    int j = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
    dp[j] = arr[i];
    ans[i] = j + 1;
}

for (int i = n - 1; i >= 0; i--) {
    int pos = lower_bound(pd.begin(), pd.end(), -(arr[i] - k)) - pd.begin();
    mx = max(mx, ans[i] + pos);
    //cout << pos << ' ';
    int insert_pos = lower_bound(pd.begin(), pd.end(), -arr[i]) - pd.begin();
    pd[insert_pos] = -arr[i];
}
//cout << endl;
cout << mx << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...