Submission #810586

#TimeUsernameProblemLanguageResultExecution timeMemory
810586welleythGlobal Warming (CEOI18_glo)C++17
100 / 100
683 ms46892 KiB
#include <bits/stdc++.h> using namespace std; constexpr int N = (int)7e5; int t[3][N]; void upd(int r,int d,int v){ for(int i = r; i < N; i |= i+1) t[v][i] = max(t[v][i],d); return; } int get(int r,int v){ int s = 0; for(int i = r; i >= 0; i &= i+1,i--){ s = max(s,t[v][i]); } return s; } void solve(){ int n,x; cin >> n >> x; int a[n+1]; set<int> st; for(int i = 1; i <= n; i++){ cin >> a[i]; st.insert(a[i]-x); st.insert(a[i]); } vector<int> v(st.begin(),st.end()); map<int,int> tr; for(auto& x : v){ tr[x] = tr.size(); } int ans = 0; for(int i = 1; i <= n; i++){ int c; c = get(tr[a[i]]-1,2); ans = max(ans,c+1); upd(tr[a[i]],c+1,2); c = get(tr[a[i]]-1,1); ans = max(ans,c+1); upd(tr[a[i]],c+1,2); c = get(tr[a[i]-x]-1,1); ans = max(ans,c+1); upd(tr[a[i]-x],c+1,1); c = get(tr[a[i]-x]-1,0); ans = max(ans,c+1); upd(tr[a[i]-x],c+1,1); c = get(tr[a[i]]-1,0); ans = max(ans,c+1); upd(tr[a[i]],c+1,0); } cout << ans << "\n"; return; } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tests = 1; for(int test = 1; test <= tests; test++){ solve(); } return 0; } /** 8 10 7 3 5 12 2 7 3 4 [ ] 1 2 2 **/
#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...