Submission #57034

#	Time	Username	Problem	Language	Result	Execution time	Memory
57034		polyfish	Krov (COCI17_krov)	C++14	70 / 140	1585 ms	132096 KiB

krov

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int INF = 1010000000;
//const int64_t INF = 10;
const int MAX_N = 100002;

class range_sum_tree {
public:
	struct node {
		int cnt;
		int64_t sum;
		node *leftChild, *rightChild;

		node() {
			sum = 0;
			cnt = 0;
			leftChild = NULL;
			rightChild = NULL;
		}

		void create_children() {
			if (leftChild==NULL) {
				leftChild = new node();
				rightChild = new node();
			}
		}
	} *root;

	range_sum_tree() {
		root = new node();
	}

	void upd(int pos, int add_sum, int add_cnt, int l, int r, node *cur) {
		//cerr << l << ' ' << r << '\n';
		if (pos<l || pos>r)
			return;
		if (pos==l && r==pos) {
			cur->sum += add_sum;
			cur->cnt += add_cnt;
			return;
		}
		int mid = (1LL * l + r) / 2;
		cur->create_children();
		upd(pos, add_sum, add_cnt, l, mid, cur->leftChild);
		upd(pos, add_sum, add_cnt, mid+1, r, cur->rightChild);
		cur->sum = cur->leftChild->sum + cur->rightChild->sum;
		cur->cnt = cur->leftChild->cnt + cur->rightChild->cnt;
	}

	int64_t get_sum(int u, int v, int l, int r, node *cur) {
		if (v<l || u>r)
			return 0;
		if (u<=l && r<=v)
			return cur->sum;
		int mid = (1LL * l + r) / 2;
		cur->create_children();
		return get_sum(u, v, l, mid, cur->leftChild)
				+ get_sum(u, v, mid+1, r, cur->rightChild);
	}

	int get_cnt(int u, int v, int l, int r, node *cur) {
		if (v<l || u>r)
			return 0;
		if (u<=l && r<=v)
			return cur->cnt;
		int mid = (1LL * l + r) / 2;
		cur->create_children();
		return get_cnt(u, v, l, mid, cur->leftChild)
				+ get_cnt(u, v, mid+1, r, cur->rightChild);
	}

	void upd(int pos, int add_sum, int add_cnt) {
		upd(pos+INF, add_sum, add_cnt, 1, 2*INF, root);
	}

	int64_t get_sum(int u, int v) {
		return get_sum(u+INF, v+INF, 1, 2*INF, root);
	}

	int get_cnt(int u, int v) {
		return get_cnt(u+INF, v+INF, 1, 2*INF, root);
	}
} L, R;
int n, x[MAX_N];

void enter() {
	cin >> n;
	for (int i=1; i<=n; ++i)
		cin >> x[i];
}

int64_t calc(int roof, int h_roof) {
	int64_t res = 0;
	res += 1LL * (h_roof - roof) * L.get_cnt(-INF, h_roof - roof) - L.get_sum(-INF, h_roof - roof);
	res += L.get_sum(h_roof - roof + 1, INF) - 1LL * (h_roof - roof) * L.get_cnt(h_roof - roof + 1, INF);
	res += 1LL * (h_roof + roof) * R.get_cnt(-INF, h_roof + roof) - R.get_sum(-INF, h_roof + roof);
	res += R.get_sum(h_roof + roof + 1, INF) - 1LL * (h_roof + roof) * R.get_cnt(h_roof + roof + 1, INF);
	return res;
}

int64_t ternary_search(int pos) {
	int l = max(pos-1, n-pos)+1, r = INF;
	while (r-l+1>=3) {
		int midL = l + (r - l + 1) / 3;
		int midR = r - (r - l + 1) / 3;
		if (calc(pos, midL) > calc(pos, midR))
			l = midL;
		else
			r = midR;
	}
	int64_t res = 1e18;
	for (int i=l; i<=r; ++i)
		res = min(res, calc(pos, i));
	return res;
}

int64_t solve() {
	int64_t res = 1e18;
	for (int i=1; i<=n; ++i)
		R.upd(x[i]+i, x[i]+i, 1);
	for (int i=1; i<=n; ++i) {
		L.upd(x[i]-i, x[i]-i, 1);
		R.upd(x[i]+i, -x[i]-i, -1);
		res = min(res, ternary_search(i));
	}
	return res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	cout << solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14