#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";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
339 ms |
9624 KB |
Output is correct |
2 |
Correct |
321 ms |
9612 KB |
Output is correct |
3 |
Correct |
315 ms |
9632 KB |
Output is correct |
4 |
Correct |
312 ms |
9660 KB |
Output is correct |
5 |
Correct |
170 ms |
6708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
3780 KB |
Output is correct |
2 |
Correct |
67 ms |
3784 KB |
Output is correct |
3 |
Correct |
87 ms |
3776 KB |
Output is correct |
4 |
Correct |
38 ms |
2484 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
41 ms |
2500 KB |
Output is correct |
7 |
Correct |
56 ms |
3744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
146 ms |
5144 KB |
Output is correct |
2 |
Correct |
170 ms |
5044 KB |
Output is correct |
3 |
Correct |
363 ms |
9708 KB |
Output is correct |
4 |
Correct |
169 ms |
6824 KB |
Output is correct |
5 |
Correct |
124 ms |
4632 KB |
Output is correct |
6 |
Correct |
169 ms |
8780 KB |
Output is correct |
7 |
Correct |
188 ms |
9420 KB |
Output is correct |
8 |
Correct |
117 ms |
5056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
339 ms |
9624 KB |
Output is correct |
28 |
Correct |
321 ms |
9612 KB |
Output is correct |
29 |
Correct |
315 ms |
9632 KB |
Output is correct |
30 |
Correct |
312 ms |
9660 KB |
Output is correct |
31 |
Correct |
170 ms |
6708 KB |
Output is correct |
32 |
Correct |
82 ms |
3780 KB |
Output is correct |
33 |
Correct |
67 ms |
3784 KB |
Output is correct |
34 |
Correct |
87 ms |
3776 KB |
Output is correct |
35 |
Correct |
38 ms |
2484 KB |
Output is correct |
36 |
Correct |
1 ms |
204 KB |
Output is correct |
37 |
Correct |
41 ms |
2500 KB |
Output is correct |
38 |
Correct |
56 ms |
3744 KB |
Output is correct |
39 |
Correct |
146 ms |
5144 KB |
Output is correct |
40 |
Correct |
170 ms |
5044 KB |
Output is correct |
41 |
Correct |
363 ms |
9708 KB |
Output is correct |
42 |
Correct |
169 ms |
6824 KB |
Output is correct |
43 |
Correct |
124 ms |
4632 KB |
Output is correct |
44 |
Correct |
169 ms |
8780 KB |
Output is correct |
45 |
Correct |
188 ms |
9420 KB |
Output is correct |
46 |
Correct |
117 ms |
5056 KB |
Output is correct |
47 |
Correct |
165 ms |
7044 KB |
Output is correct |
48 |
Correct |
156 ms |
7092 KB |
Output is correct |
49 |
Correct |
383 ms |
13728 KB |
Output is correct |
50 |
Correct |
169 ms |
8848 KB |
Output is correct |
51 |
Correct |
123 ms |
6452 KB |
Output is correct |
52 |
Correct |
186 ms |
8928 KB |
Output is correct |
53 |
Correct |
177 ms |
9092 KB |
Output is correct |
54 |
Correct |
177 ms |
9628 KB |
Output is correct |
55 |
Correct |
275 ms |
13648 KB |
Output is correct |