Submission #804544

#TimeUsernameProblemLanguageResultExecution timeMemory
804544Valaki2Global Warming (CEOI18_glo)C++14
100 / 100
63 ms7792 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back const int maxn = 2e5; int n, x; int v[1 + maxn]; int pref[1 + maxn], suff[1 + maxn]; void solve() { cin >> n >> x; for(int i = 1; i <= n; i++) { cin >> v[i]; } vector<int> d; for(int i = 1; i <= n; i++) { auto other_it = lower_bound(d.begin(), d.end(), v[i] + x); pref[i] = other_it - d.begin(); auto it = lower_bound(d.begin(), d.end(), v[i]); if(it == d.end()) { d.pb(v[i]); } else { *it = min(*it, v[i]); } } d.clear(); for(int i = 1; i <= n; i++) { v[i] = -v[i]; } for(int i = n; i >= 1; i--) { auto other_it = lower_bound(d.begin(), d.end(), v[i]); suff[i] = other_it - d.begin(); auto it = lower_bound(d.begin(), d.end(), v[i]); if(it == d.end()) { d.pb(v[i]); } else { *it = min(*it, v[i]); } } int ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, pref[i] + suff[i] + 1); } cout << ans << "\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...