#include<bits/stdc++.h>
#define taskname "glo"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 2e5 + 5;
const int INF = 2e9 + 1;
int n, X, a[lim];
namespace sub12{
void solve(){
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
for(int d = -X; d <= X; d++){
vector<int>t(n + 1), f(n + 1, INF);
for(int k = 1; k <= n; k++){
t[k] = a[k];
}
for(int k = i; k <= j; k++){
t[k] += d;
}
f[0] = -INF;
for(int k = 1; k <= n; k++){
int low = 0, high = n - 1, p;
while(low <= high){
int mid = (low + high) >> 1;
if(f[mid] < t[k]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
f[++p] = t[k];
maximize(ans, p);
}
}
}
}
cout << ans;
}
}
namespace sub4{
void solve(){
vector<int>f(n + 1, INF);
f[0] = -INF;
int ans = 0;
for(int k = 1; k <= n; k++){
int low = 0, high = n - 1, p;
while(low <= high){
int mid = (low + high) >> 1;
if(f[mid] < a[k]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
f[++p] = a[k];
maximize(ans, p);
}
cout << ans;
}
}
namespace sub6{
int f[lim], p[lim];
void solve(){
fill(p, p + lim, INF);
p[0] = -INF;
for(int i = 1; i <= n; i++){
int low = 0, high = n - 1, P;
while(low <= high){
int mid = (low + high) >> 1;
if(p[mid] < a[i]){
low = (P = mid) + 1;
}
else{
high = mid - 1;
}
}
p[++P] = a[i];
f[i] = max(f[i - 1], P);
}
int ans = f[n];
fill(p, p + lim, -INF);
p[0] = INF;
for(int i = n, pre = 0; i > 0; i--){
int low = 0, high = n - 1, P;
a[i] += X;
while(low <= high){
int mid = (low + high) >> 1;
if(p[mid] > a[i]){
low = (P = mid) + 1;
}
else{
high = mid - 1;
}
}
p[++P] = a[i];
maximize(ans, (pre = max(pre, P)) + f[i - 1]);
}
cout << ans;
}
}
namespace sub3{
void solve(){
int ans = 0;
for(int i = n; i > 0; a[i--] += X){
vector<int>f(n + 1, INF);
f[0] = -INF;
for(int k = 1; k <= n; k++){
int low = 0, high = n - 1, p;
while(low <= high){
int mid = (low + high) >> 1;
if(f[mid] < a[k]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
f[++p] = a[k];
maximize(ans, p);
}
}
cout << ans;
}
}
namespace sub57{
int N, bit[lim];
vector<vector<pair<int, int>>>per;
void roll_back(){
for(auto& [x, y] : per.back()){
bit[x] = y;
}
per.pop_back();
}
void update(int p, int x){
per.emplace_back(vector<pair<int, int>>());
for(; p <= N; p += p & -p){
per.back().emplace_back(make_pair(p, bit[p]));
maximize(bit[p], p);
}
}
int get(int p){
int ans = 0;
for(; p > 0; p -= p & -p){
maximize(ans, bit[p]);
}
return ans;
}
void solve(){
vector<int>compress;
for(int i = 1; i <= n; i++){
compress.emplace_back(a[i]);
}
compress.emplace_back(-INF);
N = compress.size();
compress.emplace_back(INF);
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
memset(bit, 0, sizeof(bit));
vector<int>f(n + 1, INF);
int ans = f[0] = -INF;
for(int i = 1; i <= n; i++){
int low = 0, high = n - 1, p;
while(low <= high){
int mid = (low + high) >> 1;
if(f[mid] < a[i]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
maximize(ans, p);
update(lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin(), p);
}
fill(f.begin(), f.end(), -INF);
f[0] = INF;
for(int i = n; i > 0; i--){
roll_back();
a[i] += X;
int low = 0, high = n - 1, p;
while(low <= high){
int mid = (low + high) >> 1;
if(f[mid] > a[i]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
maximize(ans, get(upper_bound(compress.begin(), compress.end(), a[i]) - compress.begin() - 1) + p);
}
cout << ans;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> X;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
if(n <= 50){
sub12::solve();
}
else if(n <= 1000){
sub3::solve();
}
else if(X == 0){
sub4::solve();
}
else if(X == 1000000000){
sub6::solve();
}
else{
sub57::solve();
}
}
Compilation message
glo.cpp: In function 'void sub57::roll_back()':
glo.cpp:137:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
137 | for(auto& [x, y] : per.back()){
| ^
glo.cpp: In function 'int main()':
glo.cpp:206:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void sub6::solve()':
glo.cpp:103:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
103 | p[++P] = a[i];
| ^~~
glo.cpp:85:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
85 | p[++P] = a[i];
| ^~~
glo.cpp: In function 'void sub3::solve()':
glo.cpp:126:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
126 | f[++p] = a[k];
glo.cpp: In function 'void sub12::solve()':
glo.cpp:38:14: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
38 | f[++p] = t[k];
glo.cpp: In function 'void sub4::solve()':
glo.cpp:63:11: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
63 | f[++p] = a[k];
glo.cpp: In function 'void sub57::solve()':
glo.cpp:198:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
198 | maximize(ans, get(upper_bound(compress.begin(), compress.end(), a[i]) - compress.begin() - 1) + p);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:181:10: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
181 | update(lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin(), p);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
500 KB |
Output is correct |
14 |
Correct |
66 ms |
444 KB |
Output is correct |
15 |
Correct |
27 ms |
348 KB |
Output is correct |
16 |
Correct |
26 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
500 KB |
Output is correct |
14 |
Correct |
66 ms |
444 KB |
Output is correct |
15 |
Correct |
27 ms |
348 KB |
Output is correct |
16 |
Correct |
26 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
17 ms |
348 KB |
Output is correct |
20 |
Correct |
15 ms |
348 KB |
Output is correct |
21 |
Correct |
15 ms |
344 KB |
Output is correct |
22 |
Correct |
15 ms |
348 KB |
Output is correct |
23 |
Correct |
16 ms |
348 KB |
Output is correct |
24 |
Correct |
15 ms |
480 KB |
Output is correct |
25 |
Correct |
15 ms |
348 KB |
Output is correct |
26 |
Correct |
20 ms |
464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
3288 KB |
Output is correct |
2 |
Correct |
29 ms |
3488 KB |
Output is correct |
3 |
Correct |
27 ms |
3052 KB |
Output is correct |
4 |
Correct |
28 ms |
3152 KB |
Output is correct |
5 |
Correct |
20 ms |
2744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
10128 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3412 KB |
Output is correct |
2 |
Correct |
20 ms |
3672 KB |
Output is correct |
3 |
Correct |
40 ms |
4436 KB |
Output is correct |
4 |
Correct |
30 ms |
4160 KB |
Output is correct |
5 |
Correct |
15 ms |
3672 KB |
Output is correct |
6 |
Correct |
26 ms |
3924 KB |
Output is correct |
7 |
Correct |
28 ms |
4532 KB |
Output is correct |
8 |
Correct |
17 ms |
3408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
500 KB |
Output is correct |
14 |
Correct |
66 ms |
444 KB |
Output is correct |
15 |
Correct |
27 ms |
348 KB |
Output is correct |
16 |
Correct |
26 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
17 ms |
348 KB |
Output is correct |
20 |
Correct |
15 ms |
348 KB |
Output is correct |
21 |
Correct |
15 ms |
344 KB |
Output is correct |
22 |
Correct |
15 ms |
348 KB |
Output is correct |
23 |
Correct |
16 ms |
348 KB |
Output is correct |
24 |
Correct |
15 ms |
480 KB |
Output is correct |
25 |
Correct |
15 ms |
348 KB |
Output is correct |
26 |
Correct |
20 ms |
464 KB |
Output is correct |
27 |
Correct |
28 ms |
3288 KB |
Output is correct |
28 |
Correct |
29 ms |
3488 KB |
Output is correct |
29 |
Correct |
27 ms |
3052 KB |
Output is correct |
30 |
Correct |
28 ms |
3152 KB |
Output is correct |
31 |
Correct |
20 ms |
2744 KB |
Output is correct |
32 |
Incorrect |
32 ms |
10128 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |