| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 471757 |
2021-09-10T17:17:35 Z |
rainboy |
Krov (COCI17_krov) |
C |
|
1500 ms |
80436 KB |
#pragma GCC optimize("Ofast")
#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) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (aa[i] <= a)
lower = i;
else
upper = i;
}
s = 0, c = 0;
query(tt[upper], 0, n, l, r);
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;
while (upper - lower > 1) {
int x = (lower + upper) / 2;
if (query_(aa_, tta, n, 0, i + 1, x - i) + query_(bb_, ttb, n, i + 1, n, x + i) <= query_(aa_, tta, n, 0, i + 1, x + 1 - i) + query_(bb_, ttb, n, i + 1, n, x + 1 + i))
upper = x;
else
lower = x;
}
ans = min(ans, query_(aa_, tta, n, 0, i + 1, upper - i) + query_(bb_, ttb, n, i + 1, n, upper + i));
}
printf("%lld\n", ans);
return 0;
}
Compilation message
krov.c: In function 'main':
krov.c:122:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
krov.c:124:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%d", &xx[i]);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
844 KB |
Output is correct |
| 2 |
Correct |
14 ms |
944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
884 KB |
Output is correct |
| 2 |
Correct |
14 ms |
944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1264 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1568 KB |
Output is correct |
| 2 |
Correct |
34 ms |
1612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
34 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
3484 KB |
Output is correct |
| 2 |
Correct |
77 ms |
3276 KB |
Output is correct |
| 3 |
Correct |
45 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
18404 KB |
Output is correct |
| 2 |
Correct |
493 ms |
19536 KB |
Output is correct |
| 3 |
Correct |
514 ms |
19192 KB |
Output is correct |
| 4 |
Correct |
665 ms |
23068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
845 ms |
29820 KB |
Output is correct |
| 2 |
Correct |
1059 ms |
34116 KB |
Output is correct |
| 3 |
Correct |
788 ms |
29516 KB |
Output is correct |
| 4 |
Correct |
775 ms |
28692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1584 ms |
55492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
80436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
