Submission #541282

#TimeUsernameProblemLanguageResultExecution timeMemory
541282fcwGlobal Warming (CEOI18_glo)C++17
100 / 100
398 ms14144 KiB
#include <bits/stdc++.h> #define st first #define nd second using lint = int64_t; constexpr int mod = int(1e9) + 7; constexpr int inf = 0x3f3f3f3f; constexpr int ninf = 0xcfcfcfcf; constexpr lint linf = 0x3f3f3f3f3f3f3f3f; const long double pi = acosl(-1.0); // Returns -1 if a < b, 0 if a = b and 1 if a > b. int cmp_double(double a, double b = 0, double eps = 1e-9) { return a + eps > b ? b + eps > a ? 0 : 1 : -1; } using namespace std; template<class I> vector<int> lis(const vector<I>& S) { if (S.empty()) return {}; vector<int> prev(S.size()); typedef pair<I, int> p; vector<p> res; for(int i = 0; i < (int)S.size(); i++) { // change 0 -> i for longest non-decreasing subsequence auto it = lower_bound(res.begin(), res.end(), p {S[i], i}); if (it == res.end()) res.emplace_back(), it = res.end()-1; *it = {S[i], i}; prev[i] = it == res.begin() ? 0 : (it-1)->second; } int L = res.size(), cur = res.back().second; vector<int> ans(L); while (L--) ans[L] = cur, cur = prev[cur]; return ans; } int main() { cin.tie(nullptr)->sync_with_stdio(false); //ifstream cin; //cin.open("cowjog.in"); //ofstream cout; //cout.open("cowjog.out"); int n, x; cin>>n>>x; vector<int>a(n); for(int i=0;i<n;i++) cin>>a[i]; auto solve = [&](vector<int>&v)->int{ map<int, int>dp[2]; dp[0][-inf] = 0; dp[1][-inf] = 0; for(int i=0;i<n;i++){ { int cur = v[i] + x; auto it = dp[0].lower_bound(cur); int val = prev(it)->nd + 1; it = dp[1].upper_bound(cur); if(prev(it)->nd < val){ dp[1][cur] = val; it = dp[1].lower_bound(cur); while(next(it) != dp[1].end() && next(it)->nd <= val) dp[1].erase(next(it)); } } for(int j=0;j<2;j++){ int cur = v[i] + j * x; auto it = dp[j].lower_bound(cur); if(it == dp[j].end() || it->st != cur){ int val = prev(it)->nd + 1; dp[j][cur] = val; it = dp[j].lower_bound(cur); while(next(it) != dp[j].end() && next(it)->nd <= val) dp[j].erase(next(it)); } } } return dp[1].rbegin()->nd; }; vector<int>b = a, c = a; reverse(c.begin(), c.end()); for(int i=0;i<n;i++) c[i] = -c[i]; cout<<max(solve(b), solve(c))<<"\n"; return 0; } /* [ ]Leu o problema certo??? [ ]Ver se precisa de long long [ ]Viu o limite dos fors (é n? é m?) [ ]Tamanho do vetor, será que é 2e5 em vez de 1e5?? [ ]Testar sample [ ]Testar casos de borda [ ]1LL no 1LL << i [ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?) */
#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...