이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 3e5 + 5, inf = 1e9;
int N, D;
int a[MX], id[MX];
struct segtree {
int t[4 * MX];
void update(int v, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, pos, val);
update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
}
int query(int v, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}
} t;
vector<pair<int,int>> comp;
int getId(int x) { // find < x
auto it = lower_bound(comp.begin(), comp.end(), make_pair(x, -inf));
return it - comp.begin();
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> D;
for(int i = 1; i <= N; i++) {
cin >> a[i];
comp.push_back({a[i], i});
}
comp.push_back({0, 0});
sort(comp.begin(), comp.end());
int p = 0;
for(auto [x, pos] : comp) {
id[pos] = p++;
}
set<pair<int,int>> st, tt; // last D + 1 elements, other elements before last D + 1
int ans = 0;
for(int i = 1; i <= N; i++) {
while(!tt.empty()) {
if(tt.begin()->first < st.begin()->first) {
t.update(1, 0, p, id[tt.begin()->second], 0);
tt.erase(tt.begin());
} else {
break;
}
}
st.insert({a[i], i});
int k = max(t.query(1, 0, p, 0, getId(a[i]) - 1) + 1, t.query(1, 0, p, 0, getId(a[i] + 1) - 1));
ans = max(ans, k);
t.update(1, 0, p, id[i], k);
if(i - D >= 1) {
st.erase({a[i - D], i - D});
tt.insert({a[i - D], i - D});
}
}
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... |