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;
// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
int prelis[mxn] , suflis[mxn] , ed[mxn] , a[mxn];
int n , x;
void find1(int id) {
int l = 0 , r = id;
while (l != r) {
int m = (l + r) / 2;
if (ed[m] <= a[id]) l = m + 1;
else r = m;
}
prelis[id] = r;
ed[r] = a[id];
}
void find2(int id) {
int l = 0 , r = n-id+1;
while (l != r) {
int m = (l + r) / 2;
if (ed[m] >= a[id]) l = m + 1;
else r = m;
}
suflis[id] = r;
ed[r] = a[id];
}
struct node {
int tl , tm , tr , val;
node *left , *right;
node (int l , int r) {
tl = l , tr = r , tm = (l + r) / 2;
val = -inf;
left = right = NULL;
}
void make() {
if (left == NULL) left = new node(tl , tm);
if (right == NULL) right = new node(tm+1 , tr);
}
void update(int p , int v) {
if (tl == tr) {
val = v;
return;
}
make();
if (p <= tm) left -> update(p , v);
else right -> update(p , v);
val = max(left -> val , right -> val);
}
int query(int r) {
if (tl == tr) return val;
make();
if (r <= tm) return left -> query(r);
return max(left -> val , right -> query(r));
}
};
map < int , int > mp;
int cntr;
void compress() {
set < int > comp;
for (int i = 1; i <= n; i++) {
comp.insert(a[i]);
comp.insert(a[i] + x - 1);
}
for (int i : comp) {
mp[i] = ++cntr;
}
}
int main() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ed[0] = 0;
for (int i = 1; i <= n; i++) ed[i] = inf;
ed[1] = a[1] , prelis[1] = 1;
for (int i = 2; i <= n; i++) find1(i);
for (int i = 1; i <= n; i++) ed[i] = -inf;
ed[0] = inf;
ed[1] = a[n] , suflis[n] = 1;
for (int i = n-1; i >= 1; i--) find2(i);
compress();
node *root = new node(0 , cntr);
int ans = prelis[n];
for (int i = 1; i < n; i++) {
ans = max(ans , root -> query(mp[a[i]+x-1]) + suflis[i+1]);
root -> update(mp[a[i]] , prelis[i]);
}
cout << ans << '\n';
return 0;
}
# | 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... |