Submission #1098065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098065		hippo123	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	61 ms	6856 KiB

triusis

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<int, int>
#define prr pair<pr, int>

#define f first
#define s second
#define pr pair<int, int>
#define pb push_back
const int ndim=2e5+1;
vector<int> par(ndim);
vector<int> psize(ndim);

int main(){
	int n, m; cin>>n>>m;
	vector<int> a(n), d; 
	for (int i=0; i<n; i++) cin>>a[i];
	
	for (int i=0; i<n; i++) {
		if(m*(i+1)-a[i]>=0) d.pb(m*(i+1)-a[i]);
	}
	
	//for (auto e: d) cout<<e<<" ";
	//cout<<endl;
	
	
	
	vector<int> st;
	for (int i=0; i<(int)d.size(); i++){
		if(i==0) {st.pb(d[i]); continue; }
		auto it=upper_bound(st.begin(), st.end(), d[i]); 
		int pos=upper_bound(st.begin(), st.end(), d[i])-st.begin();
		if(it==st.end()) st.pb(d[i]);
		else{
			st[pos]=d[i];
		}
		//for (auto e: st) cout<<e<<" ";
		//cout<<endl;
	}
	cout<<n-st.size()<<endl;
	
	

}

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