| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1286868 | kerem | 즐거운 채소 기르기 (JOI14_growing) | C++20 | 0 ms | 0 KiB |
#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<pii> 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]);
}
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();
}