Submission #2147822

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define RREP(i, a, b) for(int i = (a); i >= (b); i--)
#define pq priority_queue
#define P pair<int, int>
#define P2 pair<int, P>
#define P3 pair<int, P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF = 1e9, MOD = 1e9+7, around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
const int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
const ld PI = abs(acos(-1));
const int sqrtN = 512;
const int logN = 32;
const ll LINF=1e18;

int main(){
	int n; cin >> n;
	int a[200010]; for(int i = 0; i < n; i++) cin >> a[i];
	
	int c = 0;
	for(int i = 1; i < n; i++){
		if(a[i - 1] <= a[i]) continue;
		int k = lower_bound(a, a + i, a[i]) - a;
		
		if(i - k <= a[i - 1] - a[i]){
			for(int j = i; j > k; j--) swap(a[j], a[j - 1]), c++;
		}else{
			c += a[i - 1] - a[i];
			a[i] = a[i - 1];
		}
		
		//for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
	}
	
	cout << c << endl;
	return 0;
}

Submission Info

Judge Result