oj.uz

Submission #57034

# Submission time Handle Problem Language Result Execution time Memory
57034 2018-07-13T16:32:09 Z polyfish Krov (COCI17_krov) C++14
70 / 140
 1500 ms 132096 KB 
//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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 9848 KB Output is correct
2 Correct 422 ms 11064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 11064 KB Output is correct
2 Correct 432 ms 11064 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 15356 KB Output is correct
2 Correct 619 ms 15832 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 27936 KB Output is correct
2 Correct 810 ms 27936 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1098 ms 27936 KB Output is correct
2 Correct 883 ms 27936 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 52096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 52096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 52096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 52096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1580 ms 132096 KB Time limit exceeded
2 Halted 0 ms 0 KB -