이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, d; cin >> n >> d;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> v = a;
v.push_back(-1);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin();
int tree_size = 1;
while (tree_size < (int) v.size()) tree_size <<= 1;
vector<int> tree(tree_size << 1);
auto query = [&tree, tree_size] (int l, int r) {
int res = 0;
for (l += tree_size, r += tree_size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res;
};
int ans = 0;
auto update = [&tree, tree_size, &ans] (int p, int v) {
ans = max(ans, v);
for (tree[p += tree_size] = v; p >>= 1; )
tree[p] = max(tree[p << 1 | 0], tree[p << 1 | 1]);
};
set<pair<int, int>> between, past;
for (int i = 0; i < n; i++) {
update(a[i], query(0, a[i] - 1) + 1);
between.insert({a[i], i});
if (i >= d) {
between.erase({a[i - d], i - d});
past.insert({a[i - d], i - d});
while (past.size() && between.begin()->first > past.begin()->first) {
update(past.begin()->first, 0);
past.erase(past.begin());
}
}
}
cout << ans << '\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... |