| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 737997 |
2023-05-08T04:40:13 Z |
GrindMachine |
Krov (COCI17_krov) |
C++17 |
|
1500 ms |
5952 KB |
// Om Namah Shivaya
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a, b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a, b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
https://codeforces.com/blog/entry/56372?#comment-400794
made the first few observations, but didnt know how to optimize
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct fenwick {
int siz;
vector<T> tree;
fenwick(int n) {
siz = n;
tree = vector<T>(n + 1);
}
int lsb(int x) {
return x & -x;
}
void build(vector<T> &a, int n) {
for (int i = 1; i <= n; ++i) {
int par = i + lsb(i);
tree[i] += a[i];
if (par <= siz) {
tree[par] += tree[i];
}
}
}
void pupd(int i, T v) {
i++;
while (i <= siz) {
tree[i] += v;
i += lsb(i);
}
}
T sum(int i) {
i++;
T res = 0;
while (i) {
res += tree[i];
i -= lsb(i);
}
return res;
}
T query(int l, int r) {
if (l > r) return 0;
T res = sum(r) - sum(l - 1);
return res;
}
};
void solve(int test_case)
{
ll n; cin >> n;
vector<ll> a(n + 5);
rep1(i, n) cin >> a[i];
vector<ll> b1, b2;
rep1(i, n) {
b1.pb(a[i] - i);
b2.pb(a[i] + i);
}
sort(all(b1)), sort(all(b2));
b1.resize(unique(all(b1)) - b1.begin());
b2.resize(unique(all(b2)) - b2.begin());
fenwick<ll> fenw_cnt_1(n + 5), fenw_cnt_2(n + 5);
fenwick<ll> fenw_sum_1(n + 5), fenw_sum_2(n + 5);
rep1(i, n) {
ll ind = lower_bound(all(b2), a[i] + i) - b2.begin();
fenw_cnt_2.pupd(ind, 1);
fenw_sum_2.pupd(ind, a[i] + i);
}
auto get_cnt = [&](ll i, ll m) {
ll cnt = 0;
ll ind1 = upper_bound(all(b1), m - i) - b1.begin() - 1;
cnt += fenw_cnt_1.query(0, ind1);
ll ind2 = upper_bound(all(b2), m + i) - b2.begin() - 1;
cnt += fenw_cnt_2.query(0, ind2);
return cnt;
};
auto get_ops = [&](ll i, ll m) {
ll sum = 0;
ll ind = lower_bound(all(b1), m - i) - b1.begin();
ll cnt1 = fenw_cnt_1.query(ind, n);
ll sum1 = fenw_sum_1.query(ind, n);
ll cnt2 = fenw_cnt_1.query(0, ind - 1);
ll sum2 = fenw_sum_1.query(0, ind - 1);
sum += sum1 - cnt1 * (m - i);
sum += -sum2 + cnt2 * (m - i);
ind = lower_bound(all(b2), m + i) - b2.begin();
cnt1 = fenw_cnt_2.query(ind, n);
sum1 = fenw_sum_2.query(ind, n);
cnt2 = fenw_cnt_2.query(0, ind - 1);
sum2 = fenw_sum_2.query(0, ind - 1);
sum += sum1 - cnt1 * (m + i);
sum += -sum2 + cnt2 * (m + i);
return sum;
};
ll ans = inf2;
rep1(i, n) {
ll ind1 = lower_bound(all(b1), a[i] - i) - b1.begin();
ll ind2 = lower_bound(all(b2), a[i] + i) - b2.begin();
fenw_cnt_1.pupd(ind1, 1);
fenw_cnt_2.pupd(ind2, -1);
fenw_sum_1.pupd(ind1, a[i] - i);
fenw_sum_2.pupd(ind2, -(a[i] + i));
ll mxd = max((ll) i - 1, n - i);
ll l = mxd + 1, r = 2 * inf1;
ll best = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (get_cnt(i, mid) >= n / 2) {
best = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
ll ops = 0;
rep1(j, n) {
ll h = best - abs(i - j);
ops += abs(a[j] - h);
}
amin(ans, ops);
// ll ops = get_ops(i, best);
// amin(ans, ops);
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Compilation message
krov.cpp: In function 'void solve(int)':
krov.cpp:156:10: warning: variable 'get_ops' set but not used [-Wunused-but-set-variable]
156 | auto get_ops = [&](ll i, ll m) {
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
340 KB |
Output is correct |
| 2 |
Correct |
4 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
432 KB |
Output is correct |
| 2 |
Correct |
7 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
468 KB |
Output is correct |
| 2 |
Correct |
15 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
596 KB |
Output is correct |
| 2 |
Correct |
49 ms |
596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
894 ms |
1704 KB |
Output is correct |
| 2 |
Correct |
986 ms |
1780 KB |
Output is correct |
| 3 |
Incorrect |
1031 ms |
1752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1563 ms |
2632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1558 ms |
4416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1572 ms |
5952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
