제출 #967476

#제출 시각아이디문제언어결과실행 시간메모리
967476batsukh2006Global Warming (CEOI18_glo)C++17
17 / 100
668 ms42724 KiB
#include<iostream> #include<stdio.h> #include<math.h> #include<map> #include<string> #include<algorithm> #include<vector> #include<string.h> #include<utility> #include<set> #include<cmath> #include<queue> #include<deque> #include<functional> #include<stack> #include<limits.h> #include<iomanip> #include<unordered_map> #include<numeric> #include<tuple> #include<bitset> using namespace std; #define MOD 1000000007 #define int long long #define ff first #define ss second #define endl '\n' const int mxN=2e5+1; vector<int> tree(4*mxN),dp(4*mxN); vector<priority_queue<int> > s(mxN); int cal(int node, int L, int R, int l, int r){ if(L>r||R<l) return 0; if(L>=l&&R<=r) return tree[node]; return max(cal(node*2,L,(L+R)/2,l,r),cal(node*2+1,(L+R)/2+1,R,l,r)); } void up(int node, int L, int R, int p, int v){ if(L>p||R<p) return; if(L==R){ tree[node]=v; return; } up(node*2,L,(L+R)/2,p,v); up(node*2+1,(L+R)/2+1,R,p,v); tree[node]=max(tree[node*2],tree[node*2+1]); } int find(int node, int L, int R, int l, int r){ if(L>r||R<l) return 0; if(L>=l&&R<=r) return dp[node]; return max(find(node*2,L,(L+R)/2,l,r),find(node*2+1,(L+R)/2+1,R,l,r)); } void upd(int node, int L, int R, int p, int v){ if(L>p||R<p) return; if(L==R){ dp[node]=v; return; } upd(node*2,L,(L+R)/2,p,v); upd(node*2+1,(L+R)/2+1,R,p,v); dp[node]=max(dp[node*2],dp[node*2+1]); } void solve(){ int n,d; cin>>n>>d; map<int,int> mp; vector<int> a(n+1),c(n+1),f(n+1); for(int i=1; i<=n; i++) cin>>a[i],f[i]=a[i],mp[a[i]]; int k=1; for(auto& x: mp) x.ss=k++; for(int i=1; i<=n; i++) c[i]=a[i],a[i]=mp[a[i]]; for(int i=1; i<=n; i++) s[a[i]].push(0); sort(c.begin(),c.end()); for(int i=n; i>=1; i--){ int mx=find(1,1,n,a[i]+1,n); upd(1,1,n,a[i],mx+1); s[a[i]].push(mx+1); } int ans=0; for(int i=1; i<=n; i++){ s[a[i]].pop(); upd(1,1,n,a[i],s[a[i]].top()); int mx=cal(1,1,n,1,a[i]-1); up(1,1,n,a[i],mx+1); auto it=upper_bound(c.begin(),c.end(),f[i]-d); int up=it-c.begin(); up=mp[c[up+1]]; int fst=find(1,1,n,a[i]+1,n); int snd=find(1,1,n,up,a[i]); ans=max(ans,max(fst,snd)+mx+1); } cout<<ans; } signed main(){ // freopen("248.in", "r", stdin); // freopen("248.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); cout<<endl; } 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...