#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] = 1;
tail[0] = v[0];
for(int i = 1; i < v.size(); i++)
{
int pos = upper_bound(ALLR(tail), v[i] + b - 1) - tail.begin();
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(), -1);
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]);
int pos = lower_bound(tail.begin(), tail.begin() + length - 1, v[i], greater <int> ()) - tail.begin();
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:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:97:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.txt", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
