Submission #397805

#TimeUsernameProblemLanguageResultExecution timeMemory
397805sinamhdvGlobal Warming (CEOI18_glo)C++11
100 / 100
67 ms2756 KiB
// CEOI18_glo #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 2e9 + 100; const ll LINF = 1e18 + 100; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 200100 int n, x; int a[MAXN]; int fw[MAXN]; int dp[MAXN]; int32_t main(void) { fast_io; cin >> n >> x; FOR(i, 0, n) cin >> a[i]; dp[0] = INF; for (int i = n - 1; i >= 0; i--) { int pos = lower_bound(dp, dp + n + 1, a[i], greater<int>()) - dp; fw[i] = pos; dp[pos] = a[i]; } int ans = 0; fill(dp, dp + MAXN, INF); dp[0] = -INF; FOR(i, 0, n) { int pos = lower_bound(dp, dp + n + 1, a[i] + x) - dp - 1; ans = max(ans, pos + fw[i]); pos = lower_bound(dp, dp + n + 1, a[i]) - dp; dp[pos] = a[i]; } cout << ans << endl; 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...