제출 #634850

#제출 시각아이디문제언어결과실행 시간메모리
634850Morisz10Global Warming (CEOI18_glo)C++14
15 / 100
87 ms3472 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int maxn = 200010; int t[maxn], _end[maxn]; int dp[maxn]; int main() { int n, x; cin >> n >> x; for (int i = 1; i <= n; i++)cin >> t[i]; fill(dp, dp + n + 1, INT32_MAX); dp[0] = INT32_MIN; for (int i = 1; i <= n; i++) { int j = upper_bound(dp, dp + n + 1, t[i]) - dp; if (dp[j - 1] < t[i]) { dp[j] = t[i]; _end[i] = j; } else { _end[i] = j - 1; } } fill(dp, dp + n + 2, INT32_MIN); dp[0] = INT32_MAX; int ans = 0; for (int i = n; i; i--) { int l = 0, r = n; while (l + 1 < r) { int m = (l + r) / 2; if (dp[m] > t[i] - x)l = m; else r = m; } ans = max(ans, _end[i] + l); l = 0, r = n; while (l + 1 < r) { int m = (l + r) / 2; if (dp[m] > t[i])l = m; else r = m; } dp[l + 1] = t[i]; } cout << ans << 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...