#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define mp make_pair
const int N = 2*1e5+11;
int n, k, a[N], f1[N], f2[N], res;
pair <int, int> b[N];
int dp[3][N], c[N], d[N];
int upit1 (int x) {
if (x > n) x = n;
int ret = 0;
for (; x > 0; x-=x&-x) {
ret = max(ret, f1[x]);
}
return ret;
}
int upit2 (int x) {
if (x > n) x = n;
int ret = 0;
for (; x > 0; x-=x&-x) {
ret = max(ret, f2[x]);
}
return ret;
}
void ubaci1 (int x, int kol) {
for (; x <= n; x+=x&-x) {
f1[x] = max(f1[x], kol);
}
}
void ubaci2 (int x, int kol) {
for (; x <= n; x+=x&-x) {
f2[x] = max(f2[x], kol);
}
}
int main() {
cin >> n >> k;
for (int i=0;i<n;i++) {
scanf("%d", &a[i]);
b[i].ff = a[i];
b[i].ss = i;
}
sort (b, b+n);
int br = 1;
c[b[0].ss] = 1;
for (int i=1;i<n;i++) {
if (b[i].ff != b[i-1].ff) br++;
c[b[i].ss] = br;
}
int j = 0;
for (int i=1;i<n;i++) {
if (b[i].ff-k >= b[j].ff) {
while (b[i].ff-k >= b[j].ff) {
d[b[j].ss] = c[b[i-1].ss];
j++;
}
}
}
for (int i=0;i<n;i++) {
int x = c[i];
if (d[i] == 0) d[i] = n;
dp[1][i] = max(upit2(x-1), upit1(d[i]))+1;
ubaci2(x, dp[1][i]);
dp[0][i] = upit1(x-1)+1;
ubaci1(x, dp[0][i]);
res = max(res, dp[0][i]);
res = max(res, dp[1][i]);
}
cout << res;
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:51: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 |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
70 ms |
10332 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2600 KB |
Output is correct |
2 |
Correct |
22 ms |
2552 KB |
Output is correct |
3 |
Correct |
22 ms |
2552 KB |
Output is correct |
4 |
Correct |
17 ms |
2168 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
13 ms |
2216 KB |
Output is correct |
7 |
Correct |
20 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
4848 KB |
Output is correct |
2 |
Correct |
42 ms |
4816 KB |
Output is correct |
3 |
Correct |
87 ms |
9336 KB |
Output is correct |
4 |
Correct |
69 ms |
7832 KB |
Output is correct |
5 |
Correct |
28 ms |
4472 KB |
Output is correct |
6 |
Correct |
48 ms |
8156 KB |
Output is correct |
7 |
Correct |
52 ms |
8952 KB |
Output is correct |
8 |
Correct |
37 ms |
4852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |