Submission #1286860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286860		kerem	즐거운 채소 기르기 (JOI14_growing)	C++20	0 / 100	10 ms	2380 KiB

growing

#include <bits/stdc++.h>
using namespace std;
//~ #define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 300000
#define inf (int)1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

int n,ft[N+5];
void update(int x){
	for(int i=x;i<=n;i+=-i&i)
		ft[i]++;
}
int get(int x){
	int ans=0;
	for(int i=x;i>0;i-=-i&i)
		ans+=ft[i];
	return ans;
}
void solve(){
	cin >> n;
	int a[n],zip[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		zip[i]=i;
	}
	sort(zip,zip+n,[&a](int x,int y){
		return a[x]<a[y];
	});
	int say=1;
	for(int i=0;i<n;i++){
		if(i && a[zip[i]]!=a[zip[i-1]])
			say++;
		a[zip[i]]=say;
	}
	int l[n],r[n];
	memset(ft,0,sizeof(ft));
	for(int i=0;i<n;i++){
		l[i]=(i!=0?l[i-1]:0);
		l[i]+=i-get(a[i]);
		update(a[i]);
	}
	memset(ft,0,sizeof(ft));
	for(int i=n-1;i>=0;i--){
		r[i]=(i!=n-1?r[i+1]:0);
		r[i]+=(n-i-1)-get(a[i]);
		update(a[i]);
	}
	int64_t ans=n*n;
	for(int i=1;i<n;i++)
		ans=min(ans,(int64_t)l[i-1]+r[i]);
	cout << ans << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55