Submission #341584

#	Time	Username	Problem	Language	Result	Execution time	Memory
341584		nandonathaniel	Money (IZhO17_money)	C++14	45 / 100	1597 ms	61804 KiB

money

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int a[MAXN],dp[MAXN],mini,maxi,kel[MAXN],terakhir[MAXN];
 
set<int> S,active;
 
bool valid(){
	if(mini==maxi)return true;
	auto it=S.upper_bound(mini);
	auto it2=S.lower_bound(maxi);
	return it==it2;
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)cin >> a[i];
	int last=1,idx=0;
	for(int i=1;i<=n;i++){
		if(i==n || a[i]>a[i+1]){
			idx++;
			for(int j=last;j<=i;j++)kel[j]=idx;
			last=i+1;
			terakhir[idx]=i;
		}
		dp[i]=1e9;
		active.insert(i);
	}
	S.insert(0);
	S.insert(1e6+5);
	for(int i=0;i<n;i++){
		int ki=i+1,ka=terakhir[kel[i+1]],res=-1;
		mini=a[ki];
		while(ki<=ka){
			int mid=(ki+ka)/2;
			maxi=a[mid];
			if(valid()){
				res=mid;
				ki=mid+1;
			}
			else ka=mid-1;
		}
		if(res!=-1){
			//Ini gtw proofnya knp ga TLE, apa emang haram?
			//for(int j=i+1;j<=res;j++)dp[j]=min(dp[j],dp[i]+1);
			auto itL=active.lower_bound(i+1),itR=active.upper_bound(res);
			vector<int> hapus;
			for(auto it=itL;it!=itR;++it){
				dp[*it]=min(dp[*it],dp[i]+1);
				hapus.push_back(*it);
			}
			for(auto isi : hapus)active.erase(isi);
		}
		S.insert(a[i+1]);
	}
	cout << dp[n] << '\n';
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 55