Submission #949430

#TimeUsernameProblemLanguageResultExecution timeMemory
949430glebustimGlobal Warming (CEOI18_glo)C++17
100 / 100
51 ms4768 KiB
#include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(a) a.begin(), a.end() using ll = long long; using ld = long double; using pii = pair<int, int>; using vi = vector<int>; using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; const int INF = 2e9 + 10; int main() { fast; int n, x; cin >> n >> x; vi a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vi b(n + 1, INF); b[0] = -INF; vi d(n); for (int i = n - 1; i >= 0; --i) { int j = lower_bound(all(b), -a[i]) - b.begin(); b[j] = -a[i]; d[i] = j; } b.assign(n + 1, INF); b[0] = -INF; int ans = 0; for (int i = 0; i < n; ++i) { int j = lower_bound(all(b), a[i] + x) - b.begin(); ans = max(ans, d[i] + j - 1); j = lower_bound(all(b), a[i]) - b.begin(); b[j] = a[i]; } cout << ans << '\n'; }
#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...