제출 #477113

#제출 시각아이디문제언어결과실행 시간메모리
477113julian33Global Warming (CEOI18_glo)C++14
100 / 100
383 ms13728 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=4e5+5; //make sure this is right const int mod=1e9+7; struct RANK{ vector<int> all; int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;} void add(int x){all.pb(x);} void fix(){ sort(all.begin(),all.end()); all.resize(unique(all.begin(),all.end())-all.begin()); } } rnk; struct TREE{ int st[4*mxN]; void update(int v,int l,int r,int ind,int val){ if(l>ind || r<ind) return; if(l==r){ maxa(st[v],val); } else{ int m=(l+r)>>1; update(v<<1,l,m,ind,val); update(v<<1|1,m+1,r,ind,val); st[v]=max(st[v<<1],st[v<<1|1]); } } int query(int v,int l,int r,int lq,int rq){ if(lq>rq) return 0; if(l>=lq && r<=rq){ return st[v]; } int m=(l+r)>>1; return max(query(v<<1,l,m,lq,min(m,rq)),query(v<<1|1,m+1,r,max(lq,m+1),rq)); } } tree1,tree2; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,x; cin>>n>>x; vector<int> a(n),lis(n); for(int &i:a){ cin>>i; rnk.add(i); rnk.add(i-x); } rnk.fix(); int ans=0; int m=sz(rnk.all); for(int i=n-1;i>=0;i--){ int lo=rnk.get(a[i]-x); a[i]=rnk.get(a[i]); int lis=tree1.query(1,1,m,a[i]+1,m); int use=max(tree1.query(1,1,m,lo+1,m),tree2.query(1,1,m,a[i]+1,m)); maxa(ans,use+1); tree1.update(1,1,m,a[i],lis+1); tree2.update(1,1,m,a[i],use+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...