This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define LOG 19
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const ll INF=1e18;
const int iat=1e6+9;
const int mod=1e9+7;
void fast_IO()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
}
int n,x,t[iat],tx[iat],sz,store[iat];
void compress()
{
vector <int> v;
for(int i=1; i<=n; i++)
{
v.push_back(t[i]);
v.push_back(t[i]+x);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
sz=v.size();
for(int i=1; i<=n; i++)
{
tx[i]=lower_bound(v.begin(),v.end(),t[i]+x)-v.begin()+1;
t[i]=lower_bound(v.begin(),v.end(),t[i])-v.begin()+1;
}
}
struct Segment
{
int st[iat];
void init()
{
memset(st,0,sizeof(st));
}
void update(int id, int l, int r, int pos, int val)
{
if(l==r)
{
st[id]=max(st[id],val);
return;
}
int mid=(l+r)/2;
if(pos<=mid)update(2*id,l,mid,pos,val);
else update(2*id+1,mid+1,r,pos,val);
st[id]=max(st[2*id],st[2*id+1]);
}
int getMax(int id, int l, int r, int u, int v)
{
if(u>v || l>v || r<u)return 0;
if(u<=l && r<=v)return st[id];
int mid=(l+r)/2;
return max(getMax(2*id,l,mid,u,v),getMax(2*id+1,mid+1,r,u,v));
}
}tree1,tree2;
signed main()
{
fast_IO();
cin>>n>>x;
for(int i=1; i<=n; i++)cin>>t[i];
compress();
int ans=0;
for(int i=n; i>=1; i--)
{
store[i]=tree1.getMax(1,1,sz,tx[i]+1,sz)+1;
tree1.update(1,1,sz,tx[i],store[i]);
ans=max(ans,store[i]);
}
for(int i=1; i<=n; i++)
{
ans=max(ans,store[i]+tree2.getMax(1,1,sz,1,tx[i]-1));
int tmp=tree2.getMax(1,1,sz,1,t[i]-1)+1;
tree2.update(1,1,sz,t[i],tmp);
ans=max(ans,tmp);
}
cout<<ans;
}
Compilation message (stderr)
glo.cpp: In function 'void fast_IO()':
glo.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |