Submission #824278

#TimeUsernameProblemLanguageResultExecution timeMemory
824278Dec0DeddGlobal Warming (CEOI18_glo)C++14
100 / 100
518 ms58716 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") const int N = 2e5+10; struct segtree { vector<int> t; int sz; void init(int k) { sz=1; while (sz < 4*k) sz*=2; t.resize(sz+1); } void upd(int v, int l, int r, int p, int val) { if (l == r) { t[v]=max(t[v], val); return; } int m=(l+r)/2; if (p <= m) upd(2*v, l, m, p, val); else upd(2*v+1, m+1, r, p, val); t[v]=max(t[2*v], t[2*v+1]); } int que(int v, int l, int r, int ql, int qr) { if (l > qr || r < ql) return 0; if (l >= ql && r <= qr) return t[v]; int m=(l+r)/2; return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr)); } }; int a[N], b[N], n, x, pre[N], suf[N]; unordered_map<int, int> sc; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>x; set<int> st; for (int i=1; i<=n; ++i) { cin>>a[i]; st.insert(a[i]), st.insert(a[i]+x); } int i=1; for (auto u : st) sc[u]=i++; for (int i=1; i<=n; ++i) b[i]=sc[a[i]]; segtree tr2; tr2.init(2*n+10); for (int i=n; i>=1; --i) { suf[i]=tr2.que(1, 1, 2*n, b[i]+1, 2*n)+1; tr2.upd(1, 1, 2*n, b[i], suf[i]); } /* cout<<"pre: "; for (int i=1; i<=n; ++i) cout<<pre[i]<<" "; cout<<"\n"; cout<<"suf: "; for (int i=1; i<=n; ++i) cout<<suf[i]<<" "; cout<<"\n"; */ int ans=0; segtree tr; tr.init(2*n+1); for (int i=1; i+1<=n; ++i) { pre[i]=tr.que(1, 1, 2*n, 1, b[i]-1)+1; tr.upd(1, 1, 2*n, b[i], pre[i]); ans=max(ans, tr.que(1, 1, 2*n, 1, sc[a[i+1]+x]-1)+suf[i+1]); } 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...