Submission #1045152

#TimeUsernameProblemLanguageResultExecution timeMemory
1045152IdanRosenGlobal Warming (CEOI18_glo)C++98
100 / 100
43 ms8644 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll n, x; cin >> n >> x; vector<ll> arr(n); for (auto &i: arr) cin >> i; vector<ll> lis(n); { vector<ll> dp(n, -1); ll len = 0; for (ll i = 0; i < n; i++) { ll val = arr[i]; ll start = 0; ll end = len; while (start < end) { ll mid = start + (end - start) / 2; if (arr[dp[mid]] < val) start = mid + 1; else end = mid; } lis[i] = start + 1; dp[start] = i; if (start == len) ++len; } } vector<ll> lis_rev(n); { vector<ll> dp(n); ll len = 0; for (ll i = n - 1; i > 0; i--) { ll val = arr[i]; ll start = 0; ll end = len; while (start < end) { ll mid = start + (end - start) / 2; if (arr[dp[mid]] > val - x) start = mid + 1; else end = mid; } lis_rev[i] = start + 1; start = 0; end = len; while (start < end) { ll mid = start + (end - start) / 2; if (arr[dp[mid]] > val) start = mid + 1; else end = mid; } dp[start] = i; if (start == len) ++len; } } ll best_lis = 0; for (ll i = 0; i < n; i++) best_lis = max(best_lis, lis[i] + lis_rev[i] - 1); cout << best_lis; }
#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...