제출 #972250

#제출 시각아이디문제언어결과실행 시간메모리
972250sofija6Global Warming (CEOI18_glo)C++14
100 / 100
448 ms37956 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 200010 using namespace std; ll n,sz,t[MAXN],a[MAXN],l[MAXN],lisl[MAXN],lisr[MAXN]; map<ll,ll> val; set<ll> s; vector<ll> v; struct seg_tree { vector<ll> st; void Init() { st.clear(); sz=1; while (sz<n) sz <<= 1; st.resize(2*sz+2); } void Update(ll pos,ll val,ll x,ll lx,ll rx) { if (lx==rx) { st[x]=val; return; } ll mid=(lx+rx)/2; if (pos<=mid) Update(pos,val,2*x,lx,mid); else Update(pos,val,2*x+1,mid+1,rx); st[x]=max(st[2*x],st[2*x+1]); } ll Calc(ll l,ll r,ll x,ll lx,ll rx) { if (lx>r || rx<l) return 0; if (lx>=l && rx<=r) return st[x]; ll mid=(lx+rx)/2; return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx)); } }; seg_tree S; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll x,cur=1; cin >> n >> x; for (ll i=1;i<=n;i++) { cin >> t[i]; s.insert(t[i]); } for (ll i : s) { val[i]=cur++; v.push_back(i); } for (ll i : v) { auto it=upper_bound(v.begin(),v.end(),i-1+x); if (it!=v.begin()) { it--; l[val[i]]=val[*it]; } } S.Init(); for (ll i=1;i<=n;i++) { a[i]=val[t[i]]; ll maxx=0; if (a[i]!=1) maxx=S.Calc(1,a[i]-1,1,1,sz); lisl[i]=maxx+1; S.Update(a[i],maxx+1,1,1,sz); } S.Init(); for (ll i=n;i>0;i--) { ll maxx=0; if (a[i]!=n) maxx=S.Calc(a[i]+1,n,1,1,sz); lisr[i]=maxx+1; S.Update(a[i],maxx+1,1,1,sz); } S.Init(); ll ans=0; for (ll i=1;i<=n;i++) { if (l[a[i]]) ans=max(ans,S.Calc(1,l[a[i]],1,1,sz)+lisr[i]); S.Update(a[i],lisl[i],1,1,sz); } cout << ans; return 0; }
#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...