제출 #838591

#제출 시각아이디문제언어결과실행 시간메모리
838591winter0101The short shank; Redemption (BOI21_prison)C++17
0 / 100
341 ms28488 KiB
#include<bits/stdc++.h> 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 update(int id,int l,int r,int u,int val){ if (l>u||r<u)return; if (l==r){ st[id]=val; p[id]=l; return; } int mid=(l+r)/2; update(id*2,l,mid,u,val); update(id*2+1,mid+1,r,u,val); st[id]=min(st[id*2],st[id*2+1]); } int walk(int id,int l,int r,int val){ if (st[id]>val)return -1; if (l==r)return l; int mid=(l+r)/2; if (st[id*2+1]<=val)return walk(id*2+1,mid+1,r,val); return walk(id*2,l,mid,val); } 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 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,v; bool operator < (const line &p1)const { return l<p1.l; } }; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen(".OUT","w",stdout); cin>>n>>d>>t1; for1(i,1,n)cin>>a[i]; for1(i,1,n)update(1,1,n,i,inf); int prison=0; vector<line>t; for1(i,1,n){ int val=a[i]-i; int need=t1-i; if (val<=need){ update(1,1,n,i,val); prison++; continue; } int pos=walk(1,1,n,need); update(1,1,n,i,val); if (pos==-1)continue; prison++; if (t.empty()){ t.pb({pos,i-1,1}); } else { line tmp={pos,i-1,1}; while (!t.empty()&&t.back().l>=pos){ tmp.v+=t.back().v; t.pop_back(); } t.pb(tmp); } } for1(i,1,n)update(1,1,n-1,i,0); multiset<line>t2; for (auto v:t) { t2.insert(v); range_update(1,1,n-1,v.l,v.r,v.v); } vector<line>().swap(t); for1(i,1,d){ if (t2.empty())break; prison-=st[1]; int pos=p[1]; line tmp={pos,n+1,n+1}; auto it=t2.upper_bound(tmp); if (it==t2.begin())break; it--; vector<line>needtoerase; for(;;it--){ if (it==t2.begin())break; auto tp=(*it); if (tp.l<=pos&&tp.r>=pos){ needtoerase.pb(tp); range_update(1,1,n-1,tp.l,tp.r,-tp.v); } else break; } for (auto v:needtoerase)t2.erase(v); } cout<<prison; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...