제출 #1164656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164656		Jawad_Akbar_JJ	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	356 ms	165108 KiB

triusis

#include <iostream>

using namespace std;
int inf = 1e9 + 7;

struct segtree{
	segtree *lc, *rc;
	bool Lc = 0, Rc = 0;
	int Mn = inf;

	void Add(int i, int vl, int st = -inf, int en = inf){
		if (i >= en or i < st) return;
		// cout<<st<<" "<<en<<" "<<i<<" "<<vl<<'\n';
		if (en - st == 1){
			Mn = vl;
			return;
		}

		if (!Lc){
			lc = new segtree();
			rc = new segtree();
			Lc = Rc = 1;
		}
		lc->Add(i, vl, st, (st + en) / 2);
		rc->Add(i, vl, (st + en) / 2, en);
		Mn = min(lc->Mn, rc->Mn);
	}

	int get(int l, int r, int st = -inf, int en = inf){
		if (l <= st and r >= en)
			return Mn;
		if (l >= en or r <= st or Lc == 0)
			return 1e9;
		return min(lc->get(l, r, st, (st + en) / 2), rc->get(l, r, (st + en) / 2, en));
	}
};


int main(){
	// ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	segtree *Seg = new segtree();
	
	// return 0;

	int n, M, a;
	cin>>n>>M;
	int Ans = n;

	Seg->Add(0, 0);
	for (int i=1;i<=n;i++){
		cin>>a;
		int b = a - i * M;
		int dp = Seg->get(b, inf) + i - 1;
		// cout<<i<<" "<<dp<<'\n';
		// cout<<"inssert "<<b<<" "<<dp<<" "<<dp - i<<'\n';
		Ans = min(Ans, n - i + dp);
		Seg->Add(b, dp - i);
	}
	cout<<Ans<<'\n';
}

/*

5 400
300
700
200
1000
500


*/

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