이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
using ll = long long;
using ld = long double;
template<typename T>
using vv = vector<vector<T>>;
using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;
using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;
template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;
template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
const ll M = 1000000007;
const ll infll = M * M;
template<typename IN>
IN discrete_binary_search(function<bool(IN)> predicate, IN low = 0, IN high = numeric_limits<IN>::max()) {
while (low < high) {
IN middle = low + (high - low) / 2; // todo std::midpoint in cpp 2020
if (predicate(middle))
high = middle;
else low = middle + 1;
}
return low;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, x;
cin >> n >> x;
vll t(n);
F0R(i, n) cin >> t[i];
vi plis(n), slds(n);
vll idp(n+1, infll);
idp[0] = -infll;
F0R(i, n) {
*lower_bound(all(idp), t[i]-x) = t[i]-x;
plis[i] = lower_bound(all(idp), t[i]) - idp.begin();
}
vll ddp(n+1, -infll);
ddp[0] = infll;
R0F(i, n) {
int j = discrete_binary_search<int>([&](int j) -> bool {
return ddp[j] <= t[i];
}, 0, n);
ddp[j] = t[i];
slds[i] = j;
}
int res = -1;
F0R(i, n) smax(res, plis[i] + slds[i] -1);
cout << res << '\n';
}
# | 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... |