이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e6+9;
const int inf=1e9+7;
int a[maxn];
int n,d,t1;
int st[maxn*4];
int lazy[maxn*4];
int p[maxn*4];
void push(int id){
if (lazy[id]){
st[id*2]+=lazy[id];
st[id*2+1]+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void combine(int id){
st[id]=max(st[id*2],st[id*2+1]);
if (st[id*2]>st[id*2+1]){
p[id]=p[id*2];
}
else p[id]=p[id*2+1];
}
void build(int id,int l,int r){
p[id]=l;
st[id]=0;
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void range_update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id]+=val;
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id);
range_update(id*2,l,mid,u,v,val);
range_update(id*2+1,mid+1,r,u,v,val);
combine(id);
}
struct line{
int l,r;
bool operator < (const line &p1)const {
if (l==p1.l)return r<p1.r;
return l<p1.l;
}
};
bool vis[maxn];
vector<int> save[maxn*4];
vector<line>t;
void addline(int id,int l,int r,int u,int v,int dd){
if (l>v||r<u||u>v)return ;
if (u<=l&&r<=v){
save[id].pb(dd);
return;
}
int mid=(l+r)/2;
addline(id*2,l,mid,u,v,dd);
addline(id*2+1,mid+1,r,u,v,dd);
}
//vector<int>xoaxoa;
void xoa(int id,int l,int r,int u){
if (l>u||r<u)return;
//cout<<id<<" "<<l<<" "<<r<<" "<<u<<'\n';
for (auto v:save[id]){
//cerr<<v<<'\n';
//cerr<<t[v].l<<" "<<t[v].r<<'\n';
if (!vis[v]){
range_update(1,1,n-1,t[v].l,t[v].r,-1);
vis[v]=1;
}
}
if (l==r)return;
int mid=(l+r)/2;
if (mid>=u)xoa(id*2,l,mid,u);
else xoa(id*2+1,mid+1,r,u);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n>>d>>t1;
for1(i,1,n)cin>>a[i];
stack<int>hjhj;
int prison=0;
for1(i,1,n){
a[i]-=i;
int val=a[i];
int need=t1-i;
while (!hjhj.empty()&&a[hjhj.top()]>=a[i])hjhj.pop();
if (val<=need){
hjhj.push(i);
prison++;
continue;
}
while (!hjhj.empty()&&a[hjhj.top()]>need)hjhj.pop();
int pos=-1;
if (!hjhj.empty())pos=hjhj.top();
if (pos==-1)continue;
prison++;
t.pb({pos,i-1});
}
build(1,1,n-1);
for1(i,0,sz(t)-1)
{
auto v=t[i];
range_update(1,1,n-1,v.l,v.r,1);
addline(1,1,n-1,v.l,v.r,i);
}
for1(i,1,d){
if (st[1]==0)break;
prison-=st[1];
int pos=p[1];
xoa(1,1,n-1,pos);
}
cout<<prison;
}
# | 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... |