Submission #835998

#TimeUsernameProblemLanguageResultExecution timeMemory
835998enerelt14Global Warming (CEOI18_glo)C++14
0 / 100
49 ms3692 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> using namespace std; #define pb push_back const int MX = 2e5 + 5; int n, x, t[MX], num[MX]; vector<int> lis; int find(int l, int r, int val) { if(l == r) { if(lis[l] < val) return l; else return l - 1; } int mid = (l + r) / 2; if(lis[mid] < val) return find(mid + 1, r, val); else return find(l, mid, val); } int rfind(int l, int r, int val) { if(l == r) { if(lis[l] > val) return l; else return l - 1; } int mid = (l + r) / 2; if(lis[mid] > val) return rfind(mid + 1, r, val); else return rfind(l, mid, val); } int main() { ios::sync_with_stdio(0);cin.tie(0); cin >> n >> x; for(int i = 1; i <= n; i++) cin >> t[i]; num[1] = 1; lis.pb(t[1]); for(int i = 2; i <= n; i++) { num[i] = find(0, (int)lis.size() - 1, t[i]) + 2; if(num[i] == (int)lis.size() + 1) lis.pb(t[i]); else lis[num[i] - 1] = t[i]; } int ans = num[n]; lis.clear(); lis.pb(t[n] + x); for(int i = n - 1; i > 0; i--) { int k = rfind(0, (int)lis.size() - 1, t[i]) + 2; ans = max(ans, k + num[i]); k = rfind(0, (int)lis.size() - 1, t[i] + x) + 1; if(k == (int)lis.size()) lis.pb(t[i]); else lis[k] = t[i]; } cout << ans; }
#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...