Submission #1097983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097983		hippo123	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	1884 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> d(n+1);
	for (int i=1; i<=n; i++) cin>>d[i];
	d[0]=0;
	
	multiset<pr> st;
	vector<int> par(n+1);
	for (int i=0; i<=n; i++) par[i]=i;  
	
	st.insert({d[0], 0});
	
	for (int i=1; i<=n; i++){
		auto it=st.upper_bound({d[i], i});
		
		if(it==st.end()) {
			it--; par[i]=it->s; 
			st.insert({d[i], i}); 
			
		}
		else{
			st.erase(it); 
			st.insert({d[i], i});
			it=st.lower_bound({d[i], i});
			it--;
			par[i]=it->s; 	
		}
	}
	vector<int> dp(n+1, 0); 
	vector<int> ds(n+1);
	ds[0]=d[0];
	int res=0;
	for (int i=1; i<=n; i++){
		if(d[i]-ds[i-1]>m || d[i]-ds[par[i]]>m*(i-par[i])){
			//cout<<" i= "<<i<<endl;
			//cout<<" d[i]-ds[i-1]/m/ d[i]-ds[par[i]]/m*(i-par[i]="<<d[i]-ds[i-1]<<" "<<m<<" "<< d[i]-ds[par[i]]<<" "<<m*(i-par[i])<<endl;
			ds[i]=min(ds[i-1]+m, m*(i-par[i])+ds[par[i]]);
			res++;
		}
		else ds[i]=d[i];
	}
	
	cout<<res<<endl;
}

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