/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
struct item
{
int val, key, mxval;
LL prior;
item* l;
item* r;
item(int v = 0, int k = 0, LL p = rand())
{
mxval = val = v;
key = k;
prior = p;
l = r = NULL;
}
};
typedef item* pitem;
int getVal(pitem t)
{
return (!t) ? 0 : t->mxval;
}
void update(pitem t)
{
if (!t)
return;
t->mxval = max(t->val, max(getVal(t->l), getVal(t->r)));
}
void split(pitem t, int key, pitem& l, pitem& r)
{
if (!t)
l = r = NULL;
else if (t->key <= key)
{
split(t->l, key, l, t->l);
r = t;
}
else
{
split(t->r, key, t->r, r);
l = t;
}
update(t);
}
void insert(pitem& t, pitem it)
{
if (!t)
t = it;
else if (it->prior > t->prior)
{
split(t, it->key, it->l, it->r);
t = it;
}
else
insert((it->key <= t->key) ? t->l : t->r, it);
update(t);
}
void merge(pitem& t, pitem l, pitem r)
{
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
{
merge(l->r, l->r, r);
t = l;
}
else
{
merge(r->l, l, r->l);
t = r;
}
}
int get(pitem t,int key)
{
pitem l, r;
split(t, key, l, r);
int res = getVal(l);
merge(t, l, r);
return res;
}
pitem t, tx;
int n, x, mx, a[200005];
int main()
{
t = tx = NULL;
cin >> n >> x;
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
for (int i = 1; i <= n; i++)
{
insert(tx, new item(get(tx, a[i] + x - 1) + 1, a[i] + x));
insert(tx, new item(get(t, a[i] + x - 1) + 1, a[i] + x));
insert(t, new item(get(t, a[i] - 1) + 1, a[i]));
//add(1, 0, mx, a[i] + x, get(1, 0, mx, a[i] + x - 1) + 1);
//add(1, 0, mx, a[i] + x, get(0, 0, mx, a[i] + x - 1) + 1);
//add(0, 0, mx, a[i], get(0, 0, mx, a[i] - 1) + 1);
}
cout << getVal(tx) << endl;
return 0;
}
/*
3 1
1 1 3
*/
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
562 ms |
30752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
8104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
15736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
