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>
using namespace std;
constexpr int N = (int)7e5;
int t[3][N];
void upd(int r,int d,int v){
for(int i = r; i < N; i |= i+1)
t[v][i] = max(t[v][i],d);
return;
}
int get(int r,int v){
int s = 0;
for(int i = r; i >= 0; i &= i+1,i--){
s = max(s,t[v][i]);
}
return s;
}
void solve(){
int n,x;
cin >> n >> x;
int a[n+1];
set<int> st;
for(int i = 1; i <= n; i++){
cin >> a[i];
st.insert(a[i]-x);
st.insert(a[i]);
}
vector<int> v(st.begin(),st.end());
map<int,int> tr;
for(auto& x : v){
tr[x] = tr.size();
}
int ans = 0;
for(int i = 1; i <= n; i++){
int c;
c = get(tr[a[i]]-1,2);
ans = max(ans,c+1);
upd(tr[a[i]],c+1,2);
c = get(tr[a[i]]-1,1);
ans = max(ans,c+1);
upd(tr[a[i]],c+1,2);
c = get(tr[a[i]-x]-1,1);
ans = max(ans,c+1);
upd(tr[a[i]-x],c+1,1);
c = get(tr[a[i]-x]-1,0);
ans = max(ans,c+1);
upd(tr[a[i]-x],c+1,1);
c = get(tr[a[i]]-1,0);
ans = max(ans,c+1);
upd(tr[a[i]],c+1,0);
}
cout << ans << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tests = 1;
for(int test = 1; test <= tests; test++){
solve();
}
return 0;
}
/**
8 10
7 3 5 12 2 7 3 4
[ ]
1 2 2
**/
# | 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... |