#include <bits/stdc++.h>
//#include "functions.h"
#define FOR(x,y) for(int x = 0; x < y; x++)
#define ALLR(x) x.begin(),x.end()
#define con continue
#define ll long long
#define LINF LLONG_MAX
#define INF INT_MAX
#define pii pair<int,int>
#define vi vector <int>
#define pb push_back
#define F first
#define S second
#define len(x) x.length()
#define sz(x) x.size()
#define SEE(v) for(auto x : v) cout << x << " "; cout << endl;
using namespace std;
int n, b;
int CeilIndex(vi v, int l, int r, int key){
while(r - l > 1)
{
int m = l + (r - l) / 2;
if (v[m] >= key) r = m;
else l = m;
}
return r;
}
int RCeilIndex(vi v, int l, int r, int key){
while(r - l > 1)
{
int m = l + (r - l) / 2;
if(v[m] <= key) r = m;
else l = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(vi v,vi &front){
if(v.size() == 0) return 0;
vi tail(v.size(), INF);
int length = 1;
front[0] = 0;
tail[0] = v[0];
for(int i = 1; i < v.size(); i++)
{
int pos = upper_bound(ALLR(tail), v[i] + b - 1) - tail.begin();
//FOR(j, v.size()) if(tail[j] != INF) cout << tail[j] << " "; else cout << "0 ";
//cout << "Pos: " << pos << endl;
//cout << endl;
front[i] = pos;
if(v[i] < tail[0]) tail[0] = v[i];
else if(v[i] > tail[length - 1]) tail[length++] = v[i];
else tail[lower_bound(tail.begin(), tail.begin() + length - 1, v[i]) - tail.begin()] = v[i];
}
return length;
}
int LongestDecreasingSubsequenceLength(vi v, vi &back){
if (v.size() == 0) return 0;
vi tail(v.size(), 0);
int length = 1;
back[0] = 1;
tail[0] = v[0];
for(int i = 1; i < v.size(); i++)
{
int pos = RCeilIndex(tail, -1, length - 1, v[i]);
if(v[i] > tail[0]) tail[0] = v[i], back[i] = 1;
else if (v[i] < tail[length - 1]) tail[length++] = v[i], back[i] = length;
else tail[pos] = v[i], back[i] = pos + 1;
//if you are not the head, length = 0;
//back[i] = length;
}
return length;
}
int main(){
//freopen("test.txt", "r",stdin);
//int n, b;
cin >> n >> b;
vi t(n), front(n), back(n);
FOR(j, n) cin >> t[j];
int ans = LongestIncreasingSubsequenceLength(t, front);
if(b == 0)
{
cout << LongestIncreasingSubsequenceLength(t, front);
return 0;
}
reverse(ALLR(t));
LongestDecreasingSubsequenceLength(t, back);
reverse(ALLR(back));
//SEE(front);
//SEE(back);
for(int j = n - 1; j >= 0; j--) ans = max(ans, front[j] + back[j]);
cout << ans;
}
Compilation message
glo.cpp: In function 'int LongestIncreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
glo.cpp: In function 'int LongestDecreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
252 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
252 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
252 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
636 KB |
Output is correct |
20 |
Correct |
3 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
3 ms |
636 KB |
Output is correct |
23 |
Correct |
3 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
636 KB |
Output is correct |
25 |
Correct |
3 ms |
636 KB |
Output is correct |
26 |
Correct |
4 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
4476 KB |
Output is correct |
2 |
Correct |
173 ms |
4476 KB |
Output is correct |
3 |
Correct |
174 ms |
4524 KB |
Output is correct |
4 |
Correct |
177 ms |
4604 KB |
Output is correct |
5 |
Correct |
115 ms |
4604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1108 ms |
4604 KB |
Output is correct |
2 |
Correct |
1000 ms |
4604 KB |
Output is correct |
3 |
Correct |
1124 ms |
4604 KB |
Output is correct |
4 |
Correct |
1073 ms |
4604 KB |
Output is correct |
5 |
Correct |
2 ms |
4604 KB |
Output is correct |
6 |
Correct |
1054 ms |
4604 KB |
Output is correct |
7 |
Correct |
1064 ms |
4604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2057 ms |
4604 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
252 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
636 KB |
Output is correct |
20 |
Correct |
3 ms |
636 KB |
Output is correct |
21 |
Correct |
3 ms |
636 KB |
Output is correct |
22 |
Correct |
3 ms |
636 KB |
Output is correct |
23 |
Correct |
3 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
636 KB |
Output is correct |
25 |
Correct |
3 ms |
636 KB |
Output is correct |
26 |
Correct |
4 ms |
636 KB |
Output is correct |
27 |
Correct |
204 ms |
4476 KB |
Output is correct |
28 |
Correct |
173 ms |
4476 KB |
Output is correct |
29 |
Correct |
174 ms |
4524 KB |
Output is correct |
30 |
Correct |
177 ms |
4604 KB |
Output is correct |
31 |
Correct |
115 ms |
4604 KB |
Output is correct |
32 |
Correct |
1108 ms |
4604 KB |
Output is correct |
33 |
Correct |
1000 ms |
4604 KB |
Output is correct |
34 |
Correct |
1124 ms |
4604 KB |
Output is correct |
35 |
Correct |
1073 ms |
4604 KB |
Output is correct |
36 |
Correct |
2 ms |
4604 KB |
Output is correct |
37 |
Correct |
1054 ms |
4604 KB |
Output is correct |
38 |
Correct |
1064 ms |
4604 KB |
Output is correct |
39 |
Execution timed out |
2057 ms |
4604 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |