#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
const int maxv = 2e9+10;
struct Node
{
int v;
Node *l, *r;
Node()
{
v = 0;
l = r = NULL;
}
};
int n, x;
int num[maxn];
int pref[maxn], suf[maxn];
int get(Node *t) {return (t ? t->v : 0);}
void clear(Node *node, int l, int r)
{
if (!node) return;
if (l == r)
{
node->v = 0;
return;
}
int mid = (l+r)>>1;
clear(node->l, l, mid); clear(node->r, mid+1, r);
node->v = 0;
}
void upd(Node *node, int l, int r, int pos, int v)
{
if (l == r)
{
node->v = max(v, node->v);
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
{
if (!node->l) node->l = new Node();
upd(node->l, l, mid, pos, v);
}
else
{
if (!node->r) node->r = new Node();
upd(node->r, mid+1, r, pos, v);
}
node->v = max(get(node->l), get(node->r));
}
int query(Node *node, int l, int r, int a, int b)
{
if (!node || l > b || r < a) return 0;
if (l >= a && r <= b) return node->v;
int mid = (l+r)>>1;
int p1 = query(node->l, l, mid, a, b);
int p2 = query(node->r, mid+1, r, a, b);
return max(p1, p2);
}
int main(void)
{
scanf("%d %d", &n, &x);
Node *t = new Node();
for (int i = 1; i <= n; i++)
scanf("%d", &num[i]);
for (int i = 1; i <= n; i++)
{
int val = 0;
if (num[i] > 1)
val = query(t, 1, maxv-1, 1, num[i]-1);
pref[i] = val+1;
upd(t, 1, maxv-1, num[i], pref[i]);
}
clear(t, 1, maxv-1);
int ans = 0;
for (int i = n; i >= 1; i--)
{
int val = query(t, 1, maxv-1, num[i]+1, maxv-1);
suf[i] = val+1;
ans = max(ans, pref[i]+val);
upd(t, 1, maxv-1, num[i], suf[i]);
}
clear(t, 1, maxv-1);
for (int i = 1; i <= n; i++)
{
int val = 0;
if (num[i]+x > 1) val = query(t, 1, maxv-1, 1, num[i]+x-1);
ans = max(ans, suf[i]+val);
upd(t, 1, maxv-1, num[i], pref[i]);
}
printf("%d\n", ans);
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &x);
~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &num[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 |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 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 |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
256 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 |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
1024 KB |
Output is correct |
20 |
Correct |
6 ms |
1024 KB |
Output is correct |
21 |
Correct |
6 ms |
1024 KB |
Output is correct |
22 |
Correct |
6 ms |
1024 KB |
Output is correct |
23 |
Correct |
5 ms |
768 KB |
Output is correct |
24 |
Correct |
4 ms |
640 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1432 ms |
86728 KB |
Output is correct |
2 |
Correct |
1368 ms |
86776 KB |
Output is correct |
3 |
Correct |
1348 ms |
86616 KB |
Output is correct |
4 |
Correct |
1318 ms |
86732 KB |
Output is correct |
5 |
Correct |
401 ms |
47864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
24988 KB |
Output is correct |
2 |
Correct |
277 ms |
25084 KB |
Output is correct |
3 |
Correct |
294 ms |
25060 KB |
Output is correct |
4 |
Correct |
109 ms |
13816 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
69 ms |
3192 KB |
Output is correct |
7 |
Correct |
187 ms |
17992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
558 ms |
46812 KB |
Output is correct |
2 |
Correct |
622 ms |
46636 KB |
Output is correct |
3 |
Correct |
1242 ms |
86752 KB |
Output is correct |
4 |
Correct |
373 ms |
47920 KB |
Output is correct |
5 |
Correct |
130 ms |
7800 KB |
Output is correct |
6 |
Correct |
234 ms |
14456 KB |
Output is correct |
7 |
Correct |
274 ms |
14584 KB |
Output is correct |
8 |
Correct |
375 ms |
33740 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 |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
1024 KB |
Output is correct |
20 |
Correct |
6 ms |
1024 KB |
Output is correct |
21 |
Correct |
6 ms |
1024 KB |
Output is correct |
22 |
Correct |
6 ms |
1024 KB |
Output is correct |
23 |
Correct |
5 ms |
768 KB |
Output is correct |
24 |
Correct |
4 ms |
640 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
4 ms |
384 KB |
Output is correct |
27 |
Correct |
1432 ms |
86728 KB |
Output is correct |
28 |
Correct |
1368 ms |
86776 KB |
Output is correct |
29 |
Correct |
1348 ms |
86616 KB |
Output is correct |
30 |
Correct |
1318 ms |
86732 KB |
Output is correct |
31 |
Correct |
401 ms |
47864 KB |
Output is correct |
32 |
Correct |
294 ms |
24988 KB |
Output is correct |
33 |
Correct |
277 ms |
25084 KB |
Output is correct |
34 |
Correct |
294 ms |
25060 KB |
Output is correct |
35 |
Correct |
109 ms |
13816 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
69 ms |
3192 KB |
Output is correct |
38 |
Correct |
187 ms |
17992 KB |
Output is correct |
39 |
Correct |
558 ms |
46812 KB |
Output is correct |
40 |
Correct |
622 ms |
46636 KB |
Output is correct |
41 |
Correct |
1242 ms |
86752 KB |
Output is correct |
42 |
Correct |
373 ms |
47920 KB |
Output is correct |
43 |
Correct |
130 ms |
7800 KB |
Output is correct |
44 |
Correct |
234 ms |
14456 KB |
Output is correct |
45 |
Correct |
274 ms |
14584 KB |
Output is correct |
46 |
Correct |
375 ms |
33740 KB |
Output is correct |
47 |
Correct |
585 ms |
47612 KB |
Output is correct |
48 |
Correct |
641 ms |
47732 KB |
Output is correct |
49 |
Correct |
1403 ms |
88800 KB |
Output is correct |
50 |
Correct |
397 ms |
48960 KB |
Output is correct |
51 |
Correct |
207 ms |
9208 KB |
Output is correct |
52 |
Correct |
343 ms |
16504 KB |
Output is correct |
53 |
Correct |
311 ms |
16532 KB |
Output is correct |
54 |
Correct |
260 ms |
17144 KB |
Output is correct |
55 |
Correct |
953 ms |
64992 KB |
Output is correct |