제출 #583258

#제출 시각아이디문제언어결과실행 시간메모리
583258Mr_HusanboyGlobal Warming (CEOI18_glo)C++14
100 / 100
671 ms19624 KiB
// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define all(a) a.begin(), a.end() #define F first #define S second #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++) #define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--) #define vii vector<int> #define vll vector<ll> // 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively; const int inf=INT_MAX; struct segtree{ vector<int> t; int sz; void init(int n){ t.assign(4*n+5,0); sz=n; } void upd(int x, int l, int r, int ind, int val){ if(l==r){ t[x]=max(t[x],val); return; } int m=(l+r)/2; if(ind<=m){ upd(x*2,l,m,ind,val); }else upd(x*2+1,m+1,r,ind,val); t[x]=max(t[x*2],t[x*2+1]); return; } void upd(int ind, int val){ upd(1,1,sz,ind,val); } void erase(int x, int l, int r, int ind){ if(l==r){ t[x]=0;return; } int m=(l+r)/2; if(ind<=m){ erase(x*2,l,m,ind); }else erase(x*2+1,m+1,r,ind); t[x]=max(t[x*2],t[x*2+1]); return; } void erase(int ind){ erase(1,1,sz,ind); } int get(int x, int l, int r, int lx, int rx){ if(lx<=l&&r<=rx) return t[x]; if(lx>r||rx<l) return 0; int m=(l+r)/2; return max(get(x*2,l,m,lx,rx),get(x*2+1,m+1,r,lx,rx)); } int get(int l, int r){ return get(1,1,sz,l,r); } }; void solve(){ int n,x; cin>>n>>x; vector<int> a(n+1); map<int,int> mp; for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]=0; int cnt=1; for(auto &u:mp) u.S=cnt++; vector<int> l(n+1),r(n+1); segtree st; st.init(n); for(int i=1;i<=n;i++){ int ind=mp[a[i]]; l[i]=st.get(1,ind-1)+1; st.upd(ind,l[i]); } st.init(n); for(int i=n;i>0;i--){ int ind=mp[a[i]]; r[i]=st.get(ind+1,n)+1; st.upd(ind,r[i]); } vector<pair<int,int>> v(n+1); for(int i=1;i<=n;i++) v[i]={a[i],i}; sort(v.begin()+1,v.end()); vector<int> loc(n+1); for(int i=1;i<=n;i++) loc[v[i].S]=i; st.init(n); for(int i=1;i<=n;i++) st.upd(loc[i],r[i]); int ans=0; for(int i=1;i<=n;i++){ st.erase(loc[i]); int ind=upper_bound(v.begin()+1,v.end(),make_pair(a[i]-x,inf))-v.begin(); // cout<<ind<<"\n"; if(ind<=n){ ans=max(ans,l[i]+st.get(ind,n)); } } cout<<ans<<"\n"; } int main(){ ios; // int t; cin>>t; while(t--) solve(); }
#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...