이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+4;
int a[N],preflis[N],suflds[N],n,x;
vector<int>dp;
int nadjipederaalnaopacke(int x){
if(dp.empty()||x<dp.back())return dp.size();
int l=0,r=dp.size();
while(l<r){
int m=(l+r)/2;
if(dp[m]>x)
l=m+1;
else
r=m;
}
return l;
}
map<int,int>sigma,compress;
int st[4*N],ret;
void qry(int l,int r,int node=1,int tl=1,int tr=n){
if(tl>=l&&tr<=r){
ret=max(ret,sigma[st[node]]);
return;
}
int mid=(tl+tr)/2;
if(mid>=l)qry(l,r,node*2,tl,mid);
if(mid+1<=r)qry(l,r,node*2+1,mid+1,tr);
}
void upd(int id,int val,int node=1,int tl=1,int tr=n){
if(tl==tr){
st[node]=val;
return;
}
int mid=(tl+tr)/2;
if(id<=mid)upd(id,val,node*2,tl,mid);
else upd(id,val,node*2+1,mid+1,tr);
if(sigma[st[node*2]]>sigma[st[node*2+1]])st[node]=st[node*2];
else st[node]=st[node*2+1];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>x;
for(int i=0;i<n;++i)
cin>>a[i];
for(int i=0;i<n;++i){
int id=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
int sigma=-1;
if(dp.empty()||a[i]>dp.back()){
dp.push_back(a[i]);
sigma=(dp.empty()?0:dp.size()-1);
}
else dp[id]=a[i];
if(sigma==-1)sigma=id;
preflis[i]=(sigma+1);
}
dp.clear();
for(int i=n-1;i>=0;--i){
int id=nadjipederaalnaopacke(a[i]);
if(id==dp.size())dp.push_back(a[i]);
else dp[id]=a[i];
suflds[i]=(id+1);
}
int ans=dp.size();
int omikron=0;
vector<int>ljudi;
for(int i=0;i<n;++i)
ljudi.push_back(a[i]+x);
sort(ljudi.begin(),ljudi.end());
for(auto &z:ljudi)
if(!compress[z])
compress[z]=++omikron;
set<int>zeta;
fill(st,st+4*N,-1);
for(int i=n-1;i>=0;--i){
auto nx=zeta.upper_bound(a[i]);
if(nx!=zeta.end()){
int kompresovan=compress[*nx];
ret=0;
qry(kompresovan,n);
ans=max(ans,ret+preflis[i]);
}
sigma[compress[a[i]+x]]=max(sigma[compress[a[i]+x]],suflds[i]);
upd(compress[a[i]+x],compress[a[i]+x]);
zeta.insert(a[i]+x);
}
cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
glo.cpp: In function 'int main()':
glo.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if(id==dp.size())dp.push_back(a[i]);
| ~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |