#include <bits/stdc++.h>
using namespace std;
int n, x;
int a[200005], s[200005];
int suf[200005], pref[200005];
int Sol = 0;
void find_lis(int d[], int st, int dr, int sgn){
int L = 0;
memset(s, 0, sizeof(s));
for(int i = st; i != dr ; i += sgn){
a[i] = a[i] * sgn;
if(s[L] < a[i] || L == 0){
s[++L] = a[i];
d[i] = L;
}
else{
int l = 1, dr = L;
bool ok = true;
while(l <= dr){
int mij = (l + dr) / 2;
if(s[mij] == a[i]){
ok = false;
d[i] = mij;
break ;
}
if(s[mij] > a[i]) dr = mij - 1;
else l = mij + 1;
}
if(s[dr] == a[i]){
ok = false;
d[i] = dr;
}
if(!ok) continue ;
s[l] = a[i], d[i] = l;
}
}
Sol = max(Sol, L);
for(int i = 1; i <= n ; ++i) a[i] = a[i] * sgn;
}
struct node{
int val;
node *left, *right;
node(){
val = 0;
left = right = 0;
}
};
node *arb;
int query(int x, int y, int st = 1, int dr = 1e9, node *nod = arb){
if(nod == NULL) return 0;
if(x <= st && dr <= y) return nod->val;
int mij = (st + dr) / 2;
int a1 = 0, a2 = 0;
if(x <= mij) a1 = query(x, y, st, mij, nod->left);
if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod->right);
return max(a1, a2);
}
void update(int val, int pos, int st = 1, int dr = 1e9, node *nod = arb){
if(st == dr){
nod->val = val;
return ;
}
if(nod->left == NULL) nod->left = new node;
if(nod->right == NULL) nod->right = new node;
int mij = (st + dr) / 2;
if(pos <= mij){
update(val, pos, st, mij, nod->left);
}
else{
update(val, pos, mij + 1, dr, nod->right);
}
nod->val = max(nod->left->val, nod->right->val);
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d", &n, &x);
for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
find_lis(pref, 1, n + 1, 1);
find_lis(suf, n, 0, -1);
arb = new node;
update(pref[1], a[1]);
for(int i = 1; i < n ; ++i){
int aux = suf[i + 1];
aux = aux + query(max(a[i + 1] - x + 1, 1), min(a[i + 1] + x - 1, 1000000000));
Sol = max(Sol, aux);
update(pref[i + 1], a[i + 1]);
}
arb = new node;
update(suf[n], a[n]);
for(int i = n; i > 1 ; --i){
int aux = pref[i - 1];
aux = aux + query(max(a[i - 1] - x + 1, 1), min(a[i - 1] + x - 1, 1000000000));
Sol = max(Sol, aux);
update(suf[i - 1], a[i - 1]);
}
printf("%d", Sol);
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &x);
~~~~~^~~~~~~~~~~~~~~~
glo.cpp:103:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
3 ms |
1144 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1148 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1144 KB |
Output is correct |
9 |
Correct |
3 ms |
1144 KB |
Output is correct |
10 |
Correct |
3 ms |
1144 KB |
Output is correct |
11 |
Correct |
3 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
3 ms |
1144 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1148 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1144 KB |
Output is correct |
9 |
Correct |
3 ms |
1144 KB |
Output is correct |
10 |
Correct |
3 ms |
1144 KB |
Output is correct |
11 |
Correct |
3 ms |
1144 KB |
Output is correct |
12 |
Correct |
3 ms |
1144 KB |
Output is correct |
13 |
Correct |
3 ms |
1144 KB |
Output is correct |
14 |
Correct |
3 ms |
1144 KB |
Output is correct |
15 |
Correct |
3 ms |
1144 KB |
Output is correct |
16 |
Correct |
3 ms |
1144 KB |
Output is correct |
17 |
Correct |
3 ms |
1272 KB |
Output is correct |
18 |
Correct |
3 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
3 ms |
1144 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1148 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1144 KB |
Output is correct |
9 |
Correct |
3 ms |
1144 KB |
Output is correct |
10 |
Correct |
3 ms |
1144 KB |
Output is correct |
11 |
Correct |
3 ms |
1144 KB |
Output is correct |
12 |
Correct |
3 ms |
1144 KB |
Output is correct |
13 |
Correct |
3 ms |
1144 KB |
Output is correct |
14 |
Correct |
3 ms |
1144 KB |
Output is correct |
15 |
Correct |
3 ms |
1144 KB |
Output is correct |
16 |
Correct |
3 ms |
1144 KB |
Output is correct |
17 |
Correct |
3 ms |
1272 KB |
Output is correct |
18 |
Correct |
3 ms |
1144 KB |
Output is correct |
19 |
Correct |
9 ms |
3704 KB |
Output is correct |
20 |
Correct |
9 ms |
3704 KB |
Output is correct |
21 |
Correct |
9 ms |
3704 KB |
Output is correct |
22 |
Correct |
9 ms |
3708 KB |
Output is correct |
23 |
Correct |
7 ms |
2424 KB |
Output is correct |
24 |
Correct |
7 ms |
2396 KB |
Output is correct |
25 |
Correct |
4 ms |
1272 KB |
Output is correct |
26 |
Correct |
5 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
948 ms |
262148 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 |
293 ms |
92528 KB |
Output is correct |
2 |
Correct |
275 ms |
92344 KB |
Output is correct |
3 |
Correct |
282 ms |
92452 KB |
Output is correct |
4 |
Correct |
142 ms |
50168 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
89 ms |
8208 KB |
Output is correct |
7 |
Correct |
194 ms |
64508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
171284 KB |
Output is correct |
2 |
Correct |
529 ms |
171136 KB |
Output is correct |
3 |
Runtime error |
858 ms |
262148 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 |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
3 ms |
1144 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
3 ms |
1144 KB |
Output is correct |
6 |
Correct |
3 ms |
1148 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1144 KB |
Output is correct |
9 |
Correct |
3 ms |
1144 KB |
Output is correct |
10 |
Correct |
3 ms |
1144 KB |
Output is correct |
11 |
Correct |
3 ms |
1144 KB |
Output is correct |
12 |
Correct |
3 ms |
1144 KB |
Output is correct |
13 |
Correct |
3 ms |
1144 KB |
Output is correct |
14 |
Correct |
3 ms |
1144 KB |
Output is correct |
15 |
Correct |
3 ms |
1144 KB |
Output is correct |
16 |
Correct |
3 ms |
1144 KB |
Output is correct |
17 |
Correct |
3 ms |
1272 KB |
Output is correct |
18 |
Correct |
3 ms |
1144 KB |
Output is correct |
19 |
Correct |
9 ms |
3704 KB |
Output is correct |
20 |
Correct |
9 ms |
3704 KB |
Output is correct |
21 |
Correct |
9 ms |
3704 KB |
Output is correct |
22 |
Correct |
9 ms |
3708 KB |
Output is correct |
23 |
Correct |
7 ms |
2424 KB |
Output is correct |
24 |
Correct |
7 ms |
2396 KB |
Output is correct |
25 |
Correct |
4 ms |
1272 KB |
Output is correct |
26 |
Correct |
5 ms |
1272 KB |
Output is correct |
27 |
Runtime error |
948 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |