Submission #733960

#	Time	Username	Problem	Language	Result	Execution time	Memory
733960		myrcella	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	939 ms	266124 KiB

prison

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
const int maxn = 2e6+10;
int n,d,T;
int t[maxn];
int le[maxn];
int mn[maxn][21];
int lg[maxn];
 
int query(int l,int r) {
	int tmp = lg[r-l+1];
	return min(mn[l][tmp],mn[r-(1<<tmp)+1][tmp]);
}
 
pair<ll,int> tree[maxn*4],add[maxn*4];
 
void update(int c,int cl,int cr,int l,int r,ll val1,int val2) {
	if (l<=cl and cr<=r) {
		tree[c].fi += val1;
		tree[c].se += val2;
		add[c].fi += val1;
		add[c].se += val2;
		return;
	}
	int mid=cl+cr>>1;
	if (add[c]!=MP(0ll,0)) {
		tree[c<<1].fi += add[c].fi;
		tree[c<<1|1].fi += add[c].fi;
		tree[c<<1].se += add[c].se;
		tree[c<<1|1].se += add[c].se;
		add[c<<1].fi += add[c].fi, add[c<<1|1].fi += add[c].fi;
		add[c<<1].se += add[c].se, add[c<<1|1].se += add[c].se;
		add[c] = {0ll,0};
	}
	if (l<=mid) update(c<<1,cl,mid,l,r,val1,val2);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r,val1,val2);
	tree[c] = tree[c<<1];
	if (tree[c<<1|1].fi>tree[c].fi or (tree[c<<1|1].fi==tree[c].fi and tree[c<<1|1].se<tree[c].se)) tree[c] = tree[c<<1|1];
	return;
}
 
pair<ll,int> solve(int cost) {
	//the cost of installing each wall is cost
	rep(i,1,maxn*4) tree[i] = {- 1e18,0},add[i] = {0,0};
	ll tmp = 1e18;
	if (le[0]==0) tmp++;
	update(1,0,n-1,0,0,tmp,0);
	//debug((le[0]!=maxn));
	//debug(tree[1].fi);
	rep(i,1,n) {
		//install a wall here
		pair<ll,int> tmp = {tree[1].fi - cost,tree[1].se+1};
		update(1,0,n-1,i,i,1e18 + tmp.fi,tmp.se);
		if (le[i]<=i) update(1,0,n-1,le[i],i,1,0);
	}
	//cout<<cost<<" "<<tree[1].fi<<" "<<tree[1].se<<endl;
	return tree[1];
	
}
 
int main() {
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>d>>T;
	rep(i,0,n) cin>>t[i],mn[i][0] = t[i]-i;
	lg[1] = 0;
	rep(i,2,maxn) lg[i] = lg[i/2]+1;
	for (int i = n-1;i>=0;i--) 
		rep(j,1,21) {
			if (i+(1<<j)>n) break;
			mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		}
	rep(i,0,n) {
		if (t[i]<=T) le[i] = maxn;
		else {
			int l = 0,r=i;
			while (l<r) {
				int mid = l+r>>1;
				if (mid==i or query(mid,i-1)+i>T) r=mid;
				else l = mid+1;
			}
			le[i] = l;
		}
	}
	if (d==1) {
		pq <int> q;
		int cnt = 0;
		rep(i,0,n) if (le[i]==0) cnt++;
		int mx = 0;
		for (int i=n-1;i>=0;i--) {
			if (le[i]!=0) q.push({le[i]});
			while (!q.empty() and q.top()>i) q.pop();
			mx = max(mx,SZ(q));
		}
		cout<<n-cnt-mx<<"\n";
		return 0;
	}
	//monge
	int l = 0, r = n;
	pair<ll,int> ans;
	while (l<r) {
		int mid=l+r>>1;
		ans = solve(mid);
		if (ans.se<=d) r = mid;
		else l = mid+1;//penalty too small
//		cout<<ans.fi<<" "<<ans.se<<" "<<mid<<endl;
	}
	ans = solve(l);
	cout<<n-(ans.fi+d*r);
	return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void update(int, int, int, int, int, long long int, int)':
prison.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=cl+cr>>1;
      |          ~~^~~
prison.cpp: In function 'int main()':
prison.cpp:98:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     int mid = l+r>>1;
      |               ~^~
prison.cpp:122:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |   int mid=l+r>>1;
      |           ~^~

• Subtask 1: 0 / 15
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20