oj.uz

Submission #40401

# Submission time Handle Problem Language Result Execution time Memory
40401 2018-01-31T13:19:52 Z szawinis Krov (COCI17_krov) C++14
140 / 140
 398 ms 12304 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 616 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 744 KB Output is correct
2 Correct 5 ms 744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 6 ms 896 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1040 KB Output is correct
2 Correct 8 ms 1084 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1300 KB Output is correct
2 Correct 13 ms 1300 KB Output is correct
3 Correct 8 ms 1300 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 2364 KB Output is correct
2 Correct 75 ms 2364 KB Output is correct
3 Correct 109 ms 2808 KB Output is correct
4 Correct 118 ms 3080 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3736 KB Output is correct
2 Correct 177 ms 4416 KB Output is correct
3 Correct 128 ms 4520 KB Output is correct
4 Correct 129 ms 5028 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 5784 KB Output is correct
2 Correct 227 ms 7740 KB Output is correct
3 Correct 158 ms 7740 KB Output is correct
4 Correct 286 ms 8192 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 10708 KB Output is correct
2 Correct 330 ms 11544 KB Output is correct
3 Correct 302 ms 11544 KB Output is correct
4 Correct 398 ms 12304 KB Output is correct
5 Correct 79 ms 12304 KB Output is correct