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;
int n,d,ct,a[300005],seg[1200005],ans,now,indx[300005],nw[300005];
deque <int> dq;
vector <pair<int,int> > v;
priority_queue <pair<int,int> > pq,del,mn;
void update(int id,int l,int r,int pos,int v){
if (l == r)
seg[id]=v;
else
{
int mid=(l+r)/2;
if (pos <= mid) update(id*2,l,mid,pos,v);
else update(id*2+1,mid+1,r,pos,v);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
int query(int id,int l,int r,int x,int y){
if (x <= l && y >= r)
return seg[id];
if (l > y || r < x)
return -1;
int mid=(l+r)/2;
return max(query(id*2,l,mid,x,y),query(id*2+1,mid+1,r,x,y));
}
void debug(int id,int l,int r){
cerr << seg[id] << " " << l << " " << r << "\n";
if (l != r){
int mid=(l+r)/2;
debug(id*2,l,mid);
debug(id*2+1,mid+1,r);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> d;
for (int i=1;i<=n;i++){
cin >> a[i];
indx[i]=n+1;
v.push_back(make_pair(a[i],i));
}
sort(v.begin(),v.end());
for (int i=0;i<n;i++){
if (i == 0 || v[i].first != v[i-1].first) ct++;
a[v[i].second]=ct;
}
for (int i=1;i<=n;i++){
mn.push(make_pair(-a[i],i));
while (!mn.empty() && i-mn.top().second >= d){
mn.pop();
}
// cerr << i << " " << -mn.top().first << "\n";
// if (!del.empty()) cerr << -del.top().first << '\n';
while (!del.empty() && -del.top().first < -mn.top().first){
if (i-del.top().second == d)
indx[del.top().second]=i+1;
else
indx[del.top().second]=i;
del.pop();
}
if (i >= d)
del.push(make_pair(-a[i-d+1],i-d+1));
}
/* for (int i=1;i<=n;i++){
cerr << a[i] << " ";
}
cerr << "\n";
for (int i=1;i<=n;i++){
cerr << indx[i] << " ";
}
cerr << "\n";*/
for (int i=1;i<=n;i++){
while (!pq.empty() && -pq.top().first == i){
if (-pq.top().first == nw[pq.top().second])
update(1,0,ct,pq.top().second,0);
pq.pop();
}
now=max(query(1,0,ct,a[i],a[i]),query(1,0,ct,0,a[i]-1)+1);
update(1,0,ct,a[i],now);
// cerr <<i << " --- " << now << "\n";
ans=max(ans,now);
pq.push(make_pair(-indx[i],a[i]));
nw[a[i]]=indx[i];
// cout << a[i] << " " << i << " " << now << "\n";
}
cout << ans << "\n";
return 0;
}
# | 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... |