| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 471760 |
2021-09-10T17:24:50 Z |
rainboy |
Krov (COCI17_krov) |
C |
|
1461 ms |
81436 KB |
#include <stdio.h>
#define N 100000
#define LN 17 /* LN = ceil(log2(N)) */
#define N_ (1 + N * 4 + N * 2 * (LN + 1))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *zz;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (zz[ii[j]] == zz[i_])
j++;
else if (zz[ii[j]] < zz[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int ll[1 + N_], rr[1 + N_], cnt[1 + N_], _; long long sum[1 + N_];
int build(int *aa, int l, int r) {
int t_ = _++;
if (r - l == 1)
ll[t_] = 0, rr[t_] = 0, cnt[t_] = 1, sum[t_] = aa[l];
else {
int m = (l + r) / 2;
ll[t_] = build(aa, l, m), rr[t_] = build(aa, m, r);
cnt[t_] = cnt[ll[t_]] + cnt[rr[t_]];
sum[t_] = sum[ll[t_]] + sum[rr[t_]];
}
return t_;
}
int update(int t, int l, int r, int i, int c, int s) {
int t_ = _++;
if (r - l == 1)
ll[t_] = 0, rr[t_] = 0, cnt[t_] = c, sum[t_] = s;
else {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t], l, m, i, c, s), rr[t_] = rr[t];
else
ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i, c, s);
cnt[t_] = cnt[ll[t_]] + cnt[rr[t_]];
sum[t_] = sum[ll[t_]] + sum[rr[t_]];
}
return t_;
}
int c; long long s;
void query(int t, int l, int r, int ql, int qr) {
int m;
c = s = 0;
while (r - l > 1 && t != 0) {
m = (l + r) / 2;
if (ql == 0) {
if (m <= qr) {
c += cnt[ll[t]], s += sum[ll[t]];
l = m, t = rr[t];
} else
r = m, t = ll[t];
} else {
if (m >= ql) {
c += cnt[rr[t]], s += sum[rr[t]];
r = m, t = ll[t];
} else
l = m, t = rr[t];
}
}
if (t != 0 && ql <= l && r <= qr)
c += cnt[t], s += sum[t];
}
long long query_(int *aa, int *tt, int n, int l, int r, int a, long long *s_, int *c_) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (aa[i] <= a)
lower = i;
else
upper = i;
}
query(tt[upper], 0, n, l, r);
*s_ = s, *c_ = c;
return s - (long long) c * a;
}
int main() {
static int xx[N], aa[N], aa_[N], bb[N], bb_[N], ii[N], tta[N + 1], ttb[N + 1];
int n, i;
long long ans;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &xx[i]);
aa[i] = xx[i] - i, bb[i] = xx[i] + i;
}
_ = 1;
for (i = 0; i < n; i++)
ii[i] = i;
zz = aa, sort(ii, 0, n);
tta[0] = build(aa, 0, n);
for (i = 0; i < n; i++)
aa_[i] = aa[ii[i]], tta[i + 1] = update(tta[i], 0, n, ii[i], -1, -aa[ii[i]]);
for (i = 0; i < n; i++)
ii[i] = i;
zz = bb, sort(ii, 0, n);
ttb[0] = build(bb, 0, n);
for (i = 0; i < n; i++)
bb_[i] = bb[ii[i]], ttb[i + 1] = update(ttb[i], 0, n, ii[i], -1, -bb[ii[i]]);
ans = LINF;
for (i = 0; i < n; i++) {
int lower = max(i + 1, n - i) - 1, upper = INF;
long long s1, s2;
int c1, c2;
while (upper - lower > 1) {
int x = (lower + upper) / 2;
query_(aa_, tta, n, 0, i + 1, x - i, &s1, &c1);
query_(bb_, ttb, n, i + 1, n, x + i, &s2, &c2);
if (c1 + c2 <= 0)
upper = x;
else
lower = x;
}
ans = min(ans, query_(aa_, tta, n, 0, i + 1, upper - i, &s1, &c1) + query_(bb_, ttb, n, i + 1, n, upper + i, &s2, &c2));
}
printf("%lld\n", ans);
return 0;
}
Compilation message
krov.c: In function 'main':
krov.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
krov.c:123:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d", &xx[i]);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
844 KB |
Output is correct |
| 2 |
Correct |
9 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
844 KB |
Output is correct |
| 2 |
Correct |
8 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1264 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1568 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
2152 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
3480 KB |
Output is correct |
| 2 |
Correct |
52 ms |
3348 KB |
Output is correct |
| 3 |
Correct |
22 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
18408 KB |
Output is correct |
| 2 |
Correct |
317 ms |
19540 KB |
Output is correct |
| 3 |
Correct |
322 ms |
19112 KB |
Output is correct |
| 4 |
Correct |
418 ms |
23068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
530 ms |
29852 KB |
Output is correct |
| 2 |
Correct |
696 ms |
34012 KB |
Output is correct |
| 3 |
Correct |
486 ms |
29512 KB |
Output is correct |
| 4 |
Correct |
436 ms |
28696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1026 ms |
55492 KB |
Output is correct |
| 2 |
Correct |
898 ms |
59532 KB |
Output is correct |
| 3 |
Correct |
455 ms |
27800 KB |
Output is correct |
| 4 |
Correct |
1048 ms |
59688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1461 ms |
80468 KB |
Output is correct |
| 2 |
Correct |
1269 ms |
81436 KB |
Output is correct |
| 3 |
Correct |
1050 ms |
59672 KB |
Output is correct |
| 4 |
Correct |
1406 ms |
78288 KB |
Output is correct |
| 5 |
Correct |
276 ms |
19436 KB |
Output is correct |
