Submission #1164763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164763		Faisal_Saqib	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	98 ms	13640 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N=2e5+3;
int a[N],ind[N];
int n,m;
int dp[N],offset=0;
// we need to add off set to everything

void update(int i,int v)
{
	while(i<N)
	{
		dp[i]=min(dp[i],v-offset);
		i+=(i&-i);
	}
}


int query(int x)
{
	// min <=x
	int ans=n;
	while(x>0)
	{
		ans=min(ans,dp[x]);
		x-=(x&-x);
	}
	return ans+offset;
}


void solve()
{
	// statement read incorrectly
	cin>>n>>m;
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	set<ll> up;
	for(int i=0;i<=n;i++)
	{
		up.insert(i*m-a[i]);
	}
	vector<ll> cur(begin(up),end(up));
	for(int i=0;i<=n;i++)
	{
		ind[i]=lower_bound(begin(cur),end(cur),i*m-a[i])-begin(cur)+1;
	}
	for(int j=0;j<=(n+1);j++)
	{
		dp[j]=n;
	}
	update(ind[0],0);
	for(int i=0;i<n;i++)
	{

		int mn=query(ind[i+1]);
			// j*m - a[j] <= (i+1)*m - a[i+1] 
			// Fenwick
			// if((a[i+1]-v)<=m)
			// {
				// dp[i][j]
				// [i+1] never exist in dp[i]
			// 	dp[i+1][i+1]=min(dp[i+1][i+1],);
			// }

		// easy
		// for(int j=0;j<=i;j++)
		// {
		// 	// int v=a[j] + i*m - j*m;
		// 	dp[i+1][j]=min(dp[i+1][j],1+dp[i][j]);
		// }
		offset++;
		// n*m
		// m-1e9
		update(ind[i+1],mn);
	}
	// int mi=dp[n][0];
	// for(int j=1;j<=n;j++)mi=min(mi,dp[n][j]);
	cout<<query(n+1)<<endl;
}
int main()
{
	srand(time(0));
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37