Submission #1286883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286883		kerem	즐거운 채소 기르기 (JOI14_growing)	C++20	30 / 100	14 ms	5712 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];
	vector<ii> zip;
	for(int i=0;i<n;i++){
		cin >> a[i];
		zip.emb(a[i],i);
	}
	sort(all(zip));
	int say=1;
	for(int i=0;i<n;i++){
		if(i && zip[i].fr!=zip[i-1].fr)
			say++;
		a[zip[i].sc]=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]);
	}
	int ans=n*n;
	for(int i=1;i<n;i++)
		ans=min(ans,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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55