Submission #1849308

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int INF = 1e9;

int n, a[N];
int lazy[4 * N], it[4 * N];
long long res;
vector<int> val;

void build(int i, int l, int r) {
	if (l == r) {
		it[i] = val[l]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

void push(int i, int l, int r) {
	if (!lazy[i]) return;
	it[i] += lazy[i];
	if (l != r) lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0; return;
}

void upd(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return;
	if (L <= l && r <= R) {
		lazy[i] = 1, push(i, l, r); return;
	}
	int mid = (l + r) >> 1;
	upd(i << 1, l, mid, L, R);
	upd(i << 1 | 1, mid + 1, r, L, R);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return INF;
	if (L <= l && r <= R) return it[i];
	int mid = (l + r) >> 1;
	return min(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid + 1, r, L, R));
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i], val.push_back(a[i]);
	sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
	int sz = val.size();
	build(1, 0, sz - 1);
	for (int i = 1; i <= n; ++i) {
		int pos = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
		res += get(1, 0, sz - 1, pos, sz - 1) - a[i];
		upd(1, 0, sz - 1, 0, pos - 1);
	}
	cout << res;
}

Submission Info

Judge Result