This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
template <class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
const int N = 4e5 + 7, oo = 1e9 + 7;
int n, m, ans, a[N], T[4 * N], lis[N], lds[N], val[N];
void upd(int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r) {
maximize(T[id], val);
return;
}
int mid = l + r >> 1, k = id << 1;
upd(k, l, mid, pos, val); upd(k | 1, mid + 1, r, pos, val);
T[id] = max(T[k], T[k | 1]);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return -oo;
if (u <= l && r <= v) return T[id];
int mid = l + r >> 1, k = id << 1;
return max(get(k, l, mid, u, v), get(k | 1, mid + 1, r, u, v));
}
int get(int l, int r) {
return get(1, 1, N - 1, l, r);
}
void upd(int pos, int val) {
upd(1, 1, N - 1, pos, val);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
if (fopen("test.inp", "r"))
freopen("test.inp", "r", stdin);
cin >> n >> m; vector<int> v, vec;
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = -1; j <= 1; j++)
v.push_back(a[i] + j * m + abs(j));
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 1; i <= n; i++) {
val[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
int pos = lower_bound(vec.begin(), vec.end(), val[i]) - vec.begin();
if (pos == vec.size()) vec.push_back(val[i]); else vec[pos] = val[i];
lis[i] = pos + 1; maximize(ans, lis[i]);
}
vec.clear();
for (int i = n; i >= 1; i--) {
int pos = lower_bound(vec.begin(), vec.end(), -val[i]) - vec.begin();
if (pos == vec.size()) vec.push_back(-val[i]); else vec[pos] = -val[i];
lds[i] = pos + 1;
}
for (int i = n; i >= 1; i--) {
int num = lower_bound(v.begin(), v.end(), a[i] - m + 1) - v.begin() + 1;
maximize(ans, lis[i] + get(num, N - 1)); upd(val[i], lds[i]);
}
memset(T, 0, sizeof T);
for (int i = 1; i <= n; i++) {
int num = lower_bound(v.begin(), v.end(), a[i] + m + 1) - v.begin() + 1;
maximize(ans, lds[i] + get(num, N - 1)); upd(val[i], lis[i]);
}
cout << ans;
}
Compilation message (stderr)
glo.cpp: In function 'void upd(int, int, int, int, int)':
glo.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = l + r >> 1, k = id << 1;
| ~~^~~
glo.cpp: In function 'int get(int, int, int, int, int)':
glo.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = l + r >> 1, k = id << 1;
| ~~^~~
glo.cpp: In function 'int main()':
glo.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | if (pos == vec.size()) vec.push_back(val[i]); else vec[pos] = val[i];
| ~~~~^~~~~~~~~~~~~
glo.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (pos == vec.size()) vec.push_back(-val[i]); else vec[pos] = -val[i];
| ~~~~^~~~~~~~~~~~~
glo.cpp:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |