oj.uz

Submission #57033

# Submission time Handle Problem Language Result Execution time Memory
57033 2018-07-13T16:19:39 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 int64_t INF = 2010000000;
//const int64_t INF = 10;
const int64_t MAX_N = 100002;

class range_sum_tree {
public:
	struct node {
		int64_t 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(int64_t pos, int64_t add_sum, int64_t add_cnt, int64_t l, int64_t 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;
		}
		int64_t mid = (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(int64_t u, int64_t v, int64_t l, int64_t r, node *cur) {
		if (v<l || u>r)
			return 0;
		if (u<=l && r<=v)
			return cur->sum;
		int64_t mid = (l + r) / 2;
		cur->create_children();
		return get_sum(u, v, l, mid, cur->leftChild)
				+ get_sum(u, v, mid+1, r, cur->rightChild);
	}

	int64_t get_cnt(int64_t u, int64_t v, int64_t l, int64_t r, node *cur) {
		if (v<l || u>r)
			return 0;
		if (u<=l && r<=v)
			return cur->cnt;
		int64_t mid = (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(int64_t pos, int64_t add_sum, int64_t add_cnt) {
		upd(pos+INF, add_sum, add_cnt, 1LL, 2*INF, root);
	}

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

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

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

int64_t calc(int64_t roof, int64_t h_roof) {
	int64_t res = 0;
	res += (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) - (h_roof - roof) * L.get_cnt(h_roof - roof + 1, INF);
	res += (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) - (h_roof + roof) * R.get_cnt(h_roof + roof + 1, INF);
	return res;
}

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

int64_t solve() {
	int64_t res = 1e18;
	for (int64_t i=1; i<=n; ++i)
		R.upd(x[i]+i, x[i]+i, 1);
	for (int64_t 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 377 ms 10616 KB Output is correct
2 Correct 401 ms 11744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 11744 KB Output is correct
2 Correct 464 ms 12072 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 16680 KB Output is correct
2 Correct 727 ms 17064 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 27972 KB Output is correct
2 Correct 786 ms 27972 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 28360 KB Output is correct
2 Correct 1141 ms 28360 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1534 ms 45428 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 1553 ms 45428 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 1550 ms 45428 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 1598 ms 45428 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 1542 ms 132096 KB Time limit exceeded
2 Halted 0 ms 0 KB -