# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
674264 |
2022-12-23T15:21:44 Z |
rainboy |
Cake 3 (JOI19_cake3) |
C |
|
779 ms |
81236 KB |
#include <stdio.h>
#define N 200000
#define LN 18
#define N_ (N * (LN + 1) + 1)
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int vv[N], cc[N], ii[N], pp[N], n, m;
int *xx;
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 (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[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[N_], rr[N_], kk[N_]; long long ss[N_];
int update(int t, int l, int r, int i, int x) {
static int _ = 1;
int t_, m;
t_ = _++;
ll[t_] = ll[t], rr[t_] = rr[t], kk[t_] = kk[t] + 1, ss[t_] = ss[t] + x;
if (r - l > 1) {
m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t_], l, m, i, x);
else
rr[t_] = update(rr[t_], m, r, i, x);
}
return t_;
}
long long query(int t1, int t2, int k) {
if (k >= kk[t2] - kk[t1])
return ss[t2] - ss[t1];
return k < kk[rr[t2]] - kk[rr[t1]] ? query(rr[t1], rr[t2], k) : ss[rr[t2]] - ss[rr[t1]] + query(ll[t1], ll[t2], k - (kk[rr[t2]] - kk[rr[t1]]));
}
int tt[N + 1]; long long ans;
long long solve(int l1, int r1, int l2, int r2) {
int i, i_, j;
long long x_;
if (l1 > r1)
return -INF;
j = (l1 + r1) / 2;
i_ = -1, x_ = -INF;
for (i = l2; i <= r2; i++)
if (j - i + 1 >= m) {
long long x = query(tt[i], tt[j + 1], m) - (cc[ii[j]] - cc[ii[i]]) * 2;
if (x_ < x)
x_ = x, i_ = i;
}
return max(x_, max(solve(l1, j - 1, l2, i_), solve(j + 1, r1, i_, r2)));
}
int main() {
int i;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
scanf("%d%d", &vv[i], &cc[i]);
for (i = 0; i < n; i++)
ii[i] = i;
xx = vv, sort(ii, 0, n);
for (i = 0; i < n; i++)
pp[ii[i]] = i;
xx = cc, sort(ii, 0, n);
for (i = 0; i < n; i++)
tt[i + 1] = update(tt[i], 0, n, pp[ii[i]], vv[ii[i]]);
printf("%lld\n", solve(m - 1, n - 1, 0, n - 1));
return 0;
}
Compilation message
cake3.c: In function 'main':
cake3.c:86:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
cake3.c:88:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d%d", &vv[i], &cc[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
292 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
288 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
280 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
292 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
288 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
280 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
3 ms |
816 KB |
Output is correct |
39 |
Correct |
3 ms |
820 KB |
Output is correct |
40 |
Correct |
2 ms |
852 KB |
Output is correct |
41 |
Correct |
2 ms |
724 KB |
Output is correct |
42 |
Correct |
2 ms |
864 KB |
Output is correct |
43 |
Correct |
2 ms |
724 KB |
Output is correct |
44 |
Correct |
3 ms |
816 KB |
Output is correct |
45 |
Correct |
2 ms |
816 KB |
Output is correct |
46 |
Correct |
3 ms |
852 KB |
Output is correct |
47 |
Correct |
3 ms |
852 KB |
Output is correct |
48 |
Correct |
3 ms |
816 KB |
Output is correct |
49 |
Correct |
3 ms |
788 KB |
Output is correct |
50 |
Correct |
3 ms |
852 KB |
Output is correct |
51 |
Correct |
3 ms |
852 KB |
Output is correct |
52 |
Correct |
2 ms |
816 KB |
Output is correct |
53 |
Correct |
3 ms |
852 KB |
Output is correct |
54 |
Correct |
2 ms |
852 KB |
Output is correct |
55 |
Correct |
2 ms |
852 KB |
Output is correct |
56 |
Correct |
2 ms |
844 KB |
Output is correct |
57 |
Correct |
2 ms |
724 KB |
Output is correct |
58 |
Correct |
2 ms |
724 KB |
Output is correct |
59 |
Correct |
2 ms |
724 KB |
Output is correct |
60 |
Correct |
2 ms |
724 KB |
Output is correct |
61 |
Correct |
2 ms |
724 KB |
Output is correct |
62 |
Correct |
2 ms |
852 KB |
Output is correct |
63 |
Correct |
2 ms |
868 KB |
Output is correct |
64 |
Correct |
3 ms |
852 KB |
Output is correct |
65 |
Correct |
2 ms |
724 KB |
Output is correct |
66 |
Correct |
2 ms |
724 KB |
Output is correct |
67 |
Correct |
3 ms |
816 KB |
Output is correct |
68 |
Correct |
3 ms |
852 KB |
Output is correct |
69 |
Correct |
3 ms |
724 KB |
Output is correct |
70 |
Correct |
2 ms |
852 KB |
Output is correct |
71 |
Correct |
3 ms |
724 KB |
Output is correct |
72 |
Correct |
2 ms |
812 KB |
Output is correct |
73 |
Correct |
2 ms |
724 KB |
Output is correct |
74 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
288 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
292 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
288 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
280 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
3 ms |
816 KB |
Output is correct |
39 |
Correct |
3 ms |
820 KB |
Output is correct |
40 |
Correct |
2 ms |
852 KB |
Output is correct |
41 |
Correct |
2 ms |
724 KB |
Output is correct |
42 |
Correct |
2 ms |
864 KB |
Output is correct |
43 |
Correct |
2 ms |
724 KB |
Output is correct |
44 |
Correct |
3 ms |
816 KB |
Output is correct |
45 |
Correct |
2 ms |
816 KB |
Output is correct |
46 |
Correct |
3 ms |
852 KB |
Output is correct |
47 |
Correct |
3 ms |
852 KB |
Output is correct |
48 |
Correct |
3 ms |
816 KB |
Output is correct |
49 |
Correct |
3 ms |
788 KB |
Output is correct |
50 |
Correct |
3 ms |
852 KB |
Output is correct |
51 |
Correct |
3 ms |
852 KB |
Output is correct |
52 |
Correct |
2 ms |
816 KB |
Output is correct |
53 |
Correct |
3 ms |
852 KB |
Output is correct |
54 |
Correct |
2 ms |
852 KB |
Output is correct |
55 |
Correct |
2 ms |
852 KB |
Output is correct |
56 |
Correct |
2 ms |
844 KB |
Output is correct |
57 |
Correct |
2 ms |
724 KB |
Output is correct |
58 |
Correct |
2 ms |
724 KB |
Output is correct |
59 |
Correct |
2 ms |
724 KB |
Output is correct |
60 |
Correct |
2 ms |
724 KB |
Output is correct |
61 |
Correct |
2 ms |
724 KB |
Output is correct |
62 |
Correct |
2 ms |
852 KB |
Output is correct |
63 |
Correct |
2 ms |
868 KB |
Output is correct |
64 |
Correct |
3 ms |
852 KB |
Output is correct |
65 |
Correct |
2 ms |
724 KB |
Output is correct |
66 |
Correct |
2 ms |
724 KB |
Output is correct |
67 |
Correct |
3 ms |
816 KB |
Output is correct |
68 |
Correct |
3 ms |
852 KB |
Output is correct |
69 |
Correct |
3 ms |
724 KB |
Output is correct |
70 |
Correct |
2 ms |
852 KB |
Output is correct |
71 |
Correct |
3 ms |
724 KB |
Output is correct |
72 |
Correct |
2 ms |
812 KB |
Output is correct |
73 |
Correct |
2 ms |
724 KB |
Output is correct |
74 |
Correct |
2 ms |
852 KB |
Output is correct |
75 |
Correct |
738 ms |
75352 KB |
Output is correct |
76 |
Correct |
751 ms |
73164 KB |
Output is correct |
77 |
Correct |
696 ms |
75516 KB |
Output is correct |
78 |
Correct |
701 ms |
76716 KB |
Output is correct |
79 |
Correct |
222 ms |
76972 KB |
Output is correct |
80 |
Correct |
269 ms |
74664 KB |
Output is correct |
81 |
Correct |
627 ms |
75460 KB |
Output is correct |
82 |
Correct |
735 ms |
76492 KB |
Output is correct |
83 |
Correct |
779 ms |
79196 KB |
Output is correct |
84 |
Correct |
725 ms |
78924 KB |
Output is correct |
85 |
Correct |
650 ms |
76092 KB |
Output is correct |
86 |
Correct |
362 ms |
73376 KB |
Output is correct |
87 |
Correct |
382 ms |
72272 KB |
Output is correct |
88 |
Correct |
539 ms |
71888 KB |
Output is correct |
89 |
Correct |
562 ms |
76112 KB |
Output is correct |
90 |
Correct |
383 ms |
79880 KB |
Output is correct |
91 |
Correct |
304 ms |
73496 KB |
Output is correct |
92 |
Correct |
304 ms |
72856 KB |
Output is correct |
93 |
Correct |
342 ms |
76184 KB |
Output is correct |
94 |
Correct |
294 ms |
79712 KB |
Output is correct |
95 |
Correct |
395 ms |
79904 KB |
Output is correct |
96 |
Correct |
622 ms |
73904 KB |
Output is correct |
97 |
Correct |
686 ms |
80052 KB |
Output is correct |
98 |
Correct |
644 ms |
78936 KB |
Output is correct |
99 |
Correct |
574 ms |
78996 KB |
Output is correct |
100 |
Correct |
451 ms |
74232 KB |
Output is correct |
101 |
Correct |
481 ms |
74188 KB |
Output is correct |
102 |
Correct |
638 ms |
74188 KB |
Output is correct |
103 |
Correct |
576 ms |
73192 KB |
Output is correct |
104 |
Correct |
653 ms |
77456 KB |
Output is correct |
105 |
Correct |
492 ms |
77260 KB |
Output is correct |
106 |
Correct |
540 ms |
79264 KB |
Output is correct |
107 |
Correct |
494 ms |
76352 KB |
Output is correct |
108 |
Correct |
680 ms |
76168 KB |
Output is correct |
109 |
Correct |
614 ms |
80960 KB |
Output is correct |
110 |
Correct |
287 ms |
74172 KB |
Output is correct |
111 |
Correct |
341 ms |
75080 KB |
Output is correct |
112 |
Correct |
254 ms |
71552 KB |
Output is correct |
113 |
Correct |
236 ms |
81236 KB |
Output is correct |