#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(v) v.begin(), v.end()
#define pb push_back
#define int long long
using namespace std;
const int N = 1 << 19;
int dynMax[2 * N][2];
int getMax(int gauche, int droite, int mod){
if (gauche > droite) return 0;
if (gauche%2 == 1) return max(dynMax[gauche][mod], getMax(gauche + 1, droite, mod));
if (droite%2 == 0) return max(dynMax[droite][mod], getMax(gauche, droite - 1, mod));
return getMax(gauche/2, droite/2, mod);
}
void update(int ind, int val, int mod){
for (; ind > 0; ind /= 2)
chmax(dynMax[ind][mod], val);
}
signed main(){
int nVals, toAdd; cin >> nVals >> toAdd;
vector<int> triees, vals(nVals), pointeur(nVals);
map<int, int> conversion;
for (int& val : vals) cin >> val, triees.pb(val);
sort(all(triees));
pointeur[nVals - 1] = nVals - 1;
for (int ind = nVals - 2; ind >= 0; --ind){
pointeur[ind] = pointeur[ind + 1];
while (pointeur[ind] > ind && triees[pointeur[ind]] - toAdd >= triees[ind])
--pointeur[ind];
}
for (int ind = 0; ind < nVals; ++ind)conversion[triees[ind]] = ind;
for (int& val : vals) val = conversion[val];
for (int ind = 0; ind < nVals; ++ind){
for (int xAjoute = 1; xAjoute >= 0; --xAjoute){
update(N + vals[ind], getMax(N, N + vals[ind] - 1, xAjoute) + 1, xAjoute);
if (xAjoute == 1) update(N + vals[ind], getMax(N, N + pointeur[vals[ind]], 0) + 1, xAjoute);
//cout << dynMax[N + vals[ind]][xAjoute] << " " << vals[ind] << " " << pointeur[ind] << endl;
}
// cout << endl;
}
cout << max(dynMax[1][0], dynMax[1][1]) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
368 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
368 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
368 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
480 ms |
25812 KB |
Output is correct |
2 |
Correct |
448 ms |
25812 KB |
Output is correct |
3 |
Correct |
453 ms |
25940 KB |
Output is correct |
4 |
Correct |
444 ms |
25812 KB |
Output is correct |
5 |
Incorrect |
173 ms |
15700 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
6748 KB |
Output is correct |
2 |
Correct |
74 ms |
6748 KB |
Output is correct |
3 |
Correct |
73 ms |
6748 KB |
Output is correct |
4 |
Correct |
42 ms |
4316 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
44 ms |
4956 KB |
Output is correct |
7 |
Correct |
66 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
13144 KB |
Output is correct |
2 |
Correct |
176 ms |
13144 KB |
Output is correct |
3 |
Correct |
451 ms |
25956 KB |
Output is correct |
4 |
Correct |
171 ms |
15844 KB |
Output is correct |
5 |
Correct |
102 ms |
12764 KB |
Output is correct |
6 |
Correct |
200 ms |
23892 KB |
Output is correct |
7 |
Correct |
219 ms |
24536 KB |
Output is correct |
8 |
Correct |
133 ms |
13144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
368 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |