제출 #328170

#제출 시각아이디문제언어결과실행 시간메모리
328170Karen124Global Warming (CEOI18_glo)C++14
62 / 100
115 ms9856 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define F first #define S second #define pb push_back #define md ((b + e) >> 1) #define lc (ind << 1) #define rc (lc | 1) const ll N = 2e5 + 10; const ll LOG = 50; const ll MOD = 1e9 + 7; const ll INF = 1e9 + 10; ll n, add, a[N], b[N], ans; pair <ll, ll> mxl[N], mxr[N]; int main() { cin >> n >> add; for (ll i = 0; i < n; i++){ cin >> a[i]; } ll len = 0; for (ll i = 0; i < n; i++){ ll p = lower_bound(b, b + len, a[i]) - b; b[p] = a[i]; len = max(len, p + 1ll); if (i == 0) mxl[i] = {p + 1ll, -a[0]}; else mxl[i] = max(mxl[i - 1], {p + 1ll, -a[i]}); } ans = len; fill(b, b + n + 1, 0); len = 0; for (ll i = n - 1; i >= 0; i--){ ll p = lower_bound(b, b + len, -(a[i] + add)) - b; b[p] = -(a[i] + add); len = max(len, p + 1ll); if (i == n - 1) mxr[i] = {p + 1ll, a[i] + add}; else mxr[i] = max(mxr[i + 1], {p + 1ll, a[i] + add}); } for (int i = 1; i < n; i++){ if (-mxl[i - 1].S < mxr[i].S){ ans = max(ans, mxl[i - 1].F + mxr[i].F); } } cout << ans << '\n'; return 0; }
#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...