/*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 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
868 ms |
29484 KB |
Output is correct |
2 |
Correct |
902 ms |
30864 KB |
Output is correct |
3 |
Correct |
880 ms |
30840 KB |
Output is correct |
4 |
Correct |
855 ms |
30968 KB |
Output is correct |
5 |
Correct |
245 ms |
30464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
138 ms |
7672 KB |
Output is correct |
2 |
Correct |
140 ms |
8056 KB |
Output is correct |
3 |
Correct |
200 ms |
7984 KB |
Output is correct |
4 |
Correct |
52 ms |
7800 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
47 ms |
7932 KB |
Output is correct |
7 |
Correct |
90 ms |
8160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
14872 KB |
Output is correct |
2 |
Correct |
368 ms |
15864 KB |
Output is correct |
3 |
Correct |
901 ms |
31284 KB |
Output is correct |
4 |
Correct |
231 ms |
30456 KB |
Output is correct |
5 |
Correct |
105 ms |
15352 KB |
Output is correct |
6 |
Correct |
161 ms |
29012 KB |
Output is correct |
7 |
Correct |
226 ms |
29748 KB |
Output is correct |
8 |
Correct |
193 ms |
15864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |