#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31, pii = 29, piii = 41;
const int inf = 2e9 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
void readfile(){
#ifdef ONLINE_JUDGE
#else
freopen("text.inp", "r", stdin);
#endif // ONLINE_JUDGE
// freopen("cowjog.in", "r", stdin);
// freopen("cowjog.out", "w", stdout);
}
/*
consider this subsequence
a1 < a2 < ... < ai > ai+1 < ai+2 ... < aj
either increase ai+1->aj or decrease a1->ai by x
call s[i] is max lis starting with i
call e[i] is max lis ending with i
*/
int n, x;
int a[N], s[N], e[N];
vector<int> b;
unordered_map<int,int> m;
void inp(){
cin >> n >> x;
rep(i,1,n){
cin >> a[i];
if(m[a[i]]==0){
b.pb(a[i]);
m[a[i]] = 1;
}
}
sort(all(b));
}
struct seg_tree{
int sz = 1;
vector<int> val;
void inp(int n){
while(sz < n)
sz <<= 1;
val.resize(2*sz, 0);
}
void update(int x, int lx, int rx, int i, int v){
if(rx - lx == 1){
val[x] = max(val[x], v);
return;
}
int mid = (lx + rx) >> 1;
if(i < mid)
update(2*x+1,lx,mid,i,v);
else update(2*x+2,mid,rx,i,v);
val[x] = max(val[2*x+1], val[2*x+2]);
}
void update(int i, int v){
update(0,0,sz,i,v);
}
int get(int x, int lx, int rx, int l, int r){
if(r <= lx || rx <= l)
return 0;
if(l <= lx && rx <= r)
return val[x];
int mid = (lx + rx) >> 1;
int left = get(2*x+1,lx,mid,l,r);
int right = get(2*x+2,mid,rx,l,r);
return max(left, right);
}
int get(int l, int r){
return get(0, 0, sz, l, r);
}
} st;
int dp[N];
void process(){
fill(dp + 1, dp + n + 1, inf);
rep(i,1,n){
int pos = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;
dp[pos] = a[i];
e[i] = pos;
}
fill(dp + 1, dp + n + 1, -inf);
repi(i,n,1){
int l = 1, r = n, pos;
while(l <= r){
int mid = (l + r) >> 1;
if(dp[mid] <= a[i]){
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
dp[pos] = a[i];
s[i] = n + 1 - pos;
}
st.inp(n);
int res = 0;
rep(i,1,n){
int pos = upper_bound(all(b), a[i] - x) - b.begin();
int pos1 = lower_bound(all(b), a[i] + x) - b.begin() - 1;
res = max(res, st.get(pos, pos1 + 1) + s[i]);
int p = lower_bound(all(b), a[i]) - b.begin();
st.update(p, e[i]);
}
cout << res;
}
int main() {
readfile();
// TC(t){
inp();
process();
// }
return 0;
}
Compilation message
glo.cpp: In function 'void readfile()':
glo.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen("text.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void process()':
glo.cpp:127:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
127 | s[i] = n + 1 - pos;
| ~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
