#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 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]);
}
t = new Node();
for (int i = n; i >= 1; i--)
{
int val = query(t, 1, maxv-1, num[i]+1, maxv-1);
suf[i] = val+1;
upd(t, 1, maxv-1, num[i], suf[i]);
}
int ans = 0;
t = new Node();
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]);
}
t = new Node();
for (int i = n; i >= 1; i--)
{
int val = query(t, 1, maxv-1, max(1, num[i]-x+1), maxv-1);
ans = max(ans, pref[i]+val);
upd(t, 1, maxv-1, num[i], suf[i]);
}
printf("%d\n", ans);
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:65: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:70: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 |
3 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 |
3 ms |
384 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 |
3 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 |
3 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 |
3 ms |
384 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 |
3 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 |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 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 |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 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 |
3 ms |
384 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 |
3 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 |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 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 |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
8 ms |
2968 KB |
Output is correct |
| 20 |
Correct |
11 ms |
2944 KB |
Output is correct |
| 21 |
Correct |
8 ms |
2944 KB |
Output is correct |
| 22 |
Correct |
8 ms |
2972 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 25 |
Correct |
4 ms |
512 KB |
Output is correct |
| 26 |
Correct |
4 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1253 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
97316 KB |
Output is correct |
| 2 |
Correct |
335 ms |
97316 KB |
Output is correct |
| 3 |
Correct |
327 ms |
97424 KB |
Output is correct |
| 4 |
Correct |
169 ms |
52344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
96 ms |
10616 KB |
Output is correct |
| 7 |
Correct |
204 ms |
70008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
598 ms |
182056 KB |
Output is correct |
| 2 |
Correct |
687 ms |
181904 KB |
Output is correct |
| 3 |
Runtime error |
1165 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 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 |
3 ms |
384 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 |
3 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 |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 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 |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
8 ms |
2968 KB |
Output is correct |
| 20 |
Correct |
11 ms |
2944 KB |
Output is correct |
| 21 |
Correct |
8 ms |
2944 KB |
Output is correct |
| 22 |
Correct |
8 ms |
2972 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 25 |
Correct |
4 ms |
512 KB |
Output is correct |
| 26 |
Correct |
4 ms |
640 KB |
Output is correct |
| 27 |
Runtime error |
1253 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 28 |
Halted |
0 ms |
0 KB |
- |
