Submission #342981

#	Time	Username	Problem	Language	Result	Execution time	Memory
342981		David_M	Money (IZhO17_money)	C++14	100 / 100	534 ms	20076 KiB

money

#include <bits/stdc++.h>
using namespace std;
const int N=1000006;
int i,n,a[N],b[N],r[N],l[N],f[N],ans,x,y,u;
int main(){
	cin>>n;
	for (i=1; i<=n; i++)cin>>a[i],b[i]=a[i],f[a[i]]++;
	sort(b+1, b+n+1); u=a[n];
	for (i=1; i<=n; i++)r[b[i]]=b[i+1];
	for (i=n; i>=1; i--)l[b[i]]=b[i-1];
	for (i=n; i>1; i--){
		x=a[i];y=a[i-1];
		if(--f[x]==0)r[l[x]]=r[x],l[r[x]]=l[x];
		if(x==y)continue;
		if((f[x]&&x-u)||l[x]-y)ans++,u=y;
	}
	cout<<ans+1;
}

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