이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N,D;
ll arr[MAXN];
struct node {
ll s,e,m,v;
node *l, *r;
node(ll _s,ll _e){
s = _s;
e = _e;
m = (s + e) / 2;
v = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void update(ll x,ll nval){
if(s == e){
v = nval;
return;
}else{
if(x > m) r -> update(x,nval);
else l -> update(x,nval);
v = max(l -> v,r -> v);
}
}
ll rmq(ll x,ll y){
if(s == x && e == y){
return v;
}else{
if(x > m) return r -> rmq(x,y);
else if(y <= m) return l -> rmq(x,y);
else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
}
}
} *root;
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N>>D;
root = new node(0,N + 5);
vector<ll> d;
for(ll i = 0;i < N;i++){
cin>>arr[i];
d.push_back(arr[i]);
}
sort(d.begin(),d.end());
d.resize(unique(d.begin(),d.end()) - d.begin());
for(ll i = 0;i < N;i++){
arr[i] = lower_bound(d.begin(),d.end(),arr[i]) - d.begin();
}
multiset<ll> s;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
ll dp[N];
for(ll i = 0;i < N;i++){
dp[i] = 1;
}
ll ans = 0;
for(ll i = 0;i < N;i++){
while(!pq.empty() && pq.top().first < i){
s.erase(s.find(pq.top().second));
pq.pop();
}
ll maximum1 = 0, maximum2 = 0;
if(!s.empty()){
if(*s.begin() < arr[i]){
maximum1 = max(maximum1,1 + root -> rmq(*s.begin(),arr[i] - 1));
}
maximum2 = max(maximum2,1 + root -> rmq(*s.begin(),N + 5));
}
dp[i] = max({dp[i],maximum1,maximum2});
root -> update(arr[i],maximum1);
ans = max(ans,dp[i]);
pq.push({i + D,arr[i]});
s.insert(arr[i]);
}
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... |