Submission #40401

#	Time	Username	Problem	Language	Result	Execution time	Memory
40401		szawinis	Krov (COCI17_krov)	C++14	140 / 140	398 ms	12304 KiB

krov

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5;

struct fenwick {
	ll f[N];
	void update(int i, ll v) {
		++i;
		while(i < N) f[i] += v, i += i & -i;
	}
	ll query(int i) {
		++i;
		ll ret = 0;
		while(i > 0) ret += f[i], i -= i & -i;
		return ret;
	}
} chl, chr, ql, qr;

int n, h[N];
ll ans = LLONG_MAX, res[N];
vector<int> lv, rv;

int check(int i, int x) {
	int il = upper_bound(lv.begin(), lv.end(), x - i) - lv.begin() - 1;
	int ir = upper_bound(rv.begin(), rv.end(), x + i) - rv.begin() - 1;
	return chl.query(il) + chr.query(ir);
}

ll calc(ll i, ll x) {
	ll res = 0;
	int il = upper_bound(lv.begin(), lv.end(), x - i) - lv.begin() - 1;
	int ir = upper_bound(rv.begin(), rv.end(), x + i) - rv.begin() - 1;
	res += (x - i) * chl.query(il) - ql.query(il);
	res += (ql.query(n-1) - ql.query(il)) - ((x - i) * (chl.query(n-1) - chl.query(il)));
	res += (x + i) * chr.query(ir) - qr.query(ir);
	res += (qr.query(n-1) - qr.query(ir)) - ((x + i) * (chr.query(n-1) - chr.query(ir)));
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> h[i];
		lv.push_back(h[i]-i);
		rv.push_back(h[i]+i);
	}
	sort(lv.begin(), lv.end());
	sort(rv.begin(), rv.end());
	lv.resize(unique(lv.begin(), lv.end()) - lv.begin());
	rv.resize(unique(rv.begin(), rv.end()) - rv.begin());
	for(int i = 1; i <= n; i++) {
		int posr = lower_bound(rv.begin(), rv.end(), h[i] + i) - rv.begin();
		chr.update(posr, 1);
		qr.update(posr, h[i] + i);
	}
	for(int i = 1; i <= n; i++) {
		int posl = lower_bound(lv.begin(), lv.end(), h[i] - i) - lv.begin();
		int posr = lower_bound(rv.begin(), rv.end(), h[i] + i) - rv.begin();
		chl.update(posl, 1);
		ql.update(posl, h[i] - i);
		chr.update(posr, -1);
		qr.update(posr, -(h[i] + i));
		ll lb = max(i, n-i+1), rb = 1e9+2e5;
		while(lb < rb) {
			ll mid = lb+rb >> 1;
			if(check(i, mid) >= n+1 >> 1) rb = mid;
			else lb = mid+1;
		}
		ans = min(calc(i, lb), ans);
	}
	cout << ans;
}

Compilation message (stderr)

krov.cpp: In function 'int main()':
krov.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    ll mid = lb+rb >> 1;
               ^
krov.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(check(i, mid) >= n+1 >> 1) rb = mid;
                         ^

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