제출 #94453

#제출 시각아이디문제언어결과실행 시간메모리
94453Noam527Global Warming (CEOI18_glo)C++17
0 / 100
77 ms6380 KiB
#include <bits/stdc++.h> #include <unordered_set> #define CHECK cout << "ok" << endl #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7, inf = 1e9 + 7; using namespace std; void debug(string names) { cout << '\n'; } template<typename A1, typename... A2> void debug(string names, A1 par, A2... left) { int pos = 0; for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++) cout << names[pos]; cout << ": " << par << " "; while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) { pos++; } names.erase(names.begin(), names.begin() + pos); debug(names, left...); } int n, x; vector<int> a; vector<int> dp[2]; int L[2] = {}; vector<pair<int, int>> rev; int upd(int ind, int val) { int lo, hi, mid; if (ind == 0) { lo = 0, hi = L[0] + 1; while (lo < hi) { mid = (lo + hi) / 2; if (val < dp[0][mid]) hi = mid; else lo = mid + 1; } rev.push_back({ lo, dp[0][lo] }); dp[0][lo] = val; L[0] = max(L[0], lo); } else { lo = 0, hi = L[1] + 1; while (lo < hi) { mid = (lo + hi) / 2; if (val > dp[1][mid]) hi = mid; else lo = mid + 1; } dp[1][lo] = val; L[1] = max(L[1], lo); } return lo; } int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> x; a.resize(n); dp[0].resize(n + 1, 2 * inf), dp[1].resize(n + 1, -2 * inf); dp[0][0] = -2 * inf; dp[1][0] = 2 * inf; for (auto &i : a) cin >> i, upd(0, i); int ans = L[0]; for (int i = n - 1, pos1, pos0; i >= 0; i--) { pos1 = upd(1, a[i]); pos0 = rev.back().first; dp[0][rev.back().first] = rev.back().second; if (rev.back().second == 2 * inf) L[0]--; rev.pop_back(); // cout << "i " << i << '\n'; // for (int j = 0; j <= L[0] + 1; j++) cout << dp[0][j] << " "; cout << '\n'; // for (int j = 0; j <= L[1] + 1; j++) cout << dp[1][j] << " "; cout << '\n'; int lo, hi, mid; lo = 0, hi = L[1]; while (lo < hi) { mid = (lo + hi + 1) / 2; if (dp[0][pos0] - x < dp[1][mid]) lo = mid; else hi = mid - 1; } // cout << "try 1: " << pos0 << " + " << lo << '\n'; ans = max(ans, pos0 + lo); lo = 0, hi = L[0]; while (lo < hi) { mid = (lo + hi + 1) / 2; if (dp[1][pos1] + x > dp[0][mid]) lo = mid; else hi = mid - 1; } // cout << "try 2: " << pos1 << " + " << lo << '\n'; ans = max(ans, pos1 + lo); } finish(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...