#include <stdio.h>
#include <string.h>
#define N 250000
#define LN 18 /* LN = ceil(log2(N)) */
#define N_ (N * (LN + 1) + 1)
#define INF 0x3f3f3f3f3f3f3f3fLL
int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
long long xx[N + 1]; int yy[N], yy_[N], n, m, k;
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 (yy[ii[j]] == yy[i_])
j++;
else if (yy[ii[j]] < yy[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) {
static int _ = 1;
int t_ = _++;
ll[t_] = ll[t], rr[t_] = rr[t], kk[t_] = kk[t] + 1, ss[t_] = ss[t] + yy_[i];
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t_], l, m, i);
else
rr[t_] = update(rr[t_], m, r, i);
}
return t_;
}
long long s_; int y_;
void query(int t1, int t2, int l, int r, int k) {
int m;
if (r - l == 1) {
s_ += (long long) yy_[l] * k, y_ = l;
return;
}
m = (l + r) / 2;
if (k <= kk[rr[t2]] - kk[rr[t1]])
query(rr[t1], rr[t2], m, r, k);
else
s_ += ss[rr[t2]] - ss[rr[t1]], query(ll[t1], ll[t2], l, m, k - (kk[rr[t2]] - kk[rr[t1]]));
}
int tt[N + 1];
long long f(int i, int j) {
s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
return s_ - (xx[j] - xx[i]);
}
int find_j(int i1, int i2) {
int lower = i2 + k - 1, upper = n + 1;
while (upper - lower > 1) {
int j = (lower + upper) / 2;
if (f(i1, j) <= f(i2, j))
upper = j;
else
lower = j;
}
return upper;
}
int find_i(int j1, int j2) {
int lower = -1, upper = j1 - k + 1;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (f(i, j1) >= f(i, j2))
lower = i;
else
upper = i;
}
return lower;
}
int st[N_ * 2], n_;
void build() {
n_ = 1;
while (n_ < n)
n_ <<= 1;
memset(st, 0x3f, n_ * 2 * sizeof *st);
}
void update_(int l, int r, int y) {
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
st[l] = min(st[l], y), l++;
if ((r & 1) == 0)
st[r] = min(st[r], y), r--;
}
}
int main() {
static int ii[N + 1], jj[N + 1], qu[N + 1], ii_[N + 1], jj_[N + 1];
static long long xxj[N + 1], xxi[N + 1];
static char cc[N + 1];
int head, cnt, i, j, y;
long long x_;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)
scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
for (i = 0; i < n; i++)
scanf("%d", &yy[i]);
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
for (i = 0, m = 0; i < n; i = j) {
j = i, y = yy[ii[i]];
while (j < n && yy[ii[j]] == y)
yy[ii[j++]] = m;
yy_[m++] = y;
}
for (i = 0; i < n; i++)
tt[i + 1] = update(tt[i], 0, m, yy[i]);
x_ = -INF;
head = 0, cnt = 0;
for (j = k; j <= n; j++) {
while (cnt >= 2 && jj[head] <= j)
head++, cnt--;
i = j - k;
while (cnt >= 2 && f(i, jj[head + cnt - 2]) >= f(qu[head + cnt - 1], jj[head + cnt - 2]))
cnt--;
if (cnt)
jj[head + cnt - 1] = find_j(qu[head + cnt - 1], i);
qu[head + cnt++] = i;
while (cnt >= 2 && jj[head] <= j)
head++, cnt--;
i = qu[head];
ii_[j] = i, xxj[j] = f(i, j);
x_ = max(x_, xxj[j]);
}
head = 0, cnt = 0;
for (i = n - k; i >= 0; i--) {
while (cnt >= 2 && ii[head] >= i)
head++, cnt--;
j = i + k;
while (cnt >= 2 && f(ii[head + cnt - 2], j) >= f(ii[head + cnt - 2], qu[head + cnt - 1]))
cnt--;
if (cnt)
ii[head + cnt - 1] = find_i(j, qu[head + cnt - 1]);
qu[head + cnt++] = j;
while (cnt >= 2 && ii[head] >= i)
head++, cnt--;
j = qu[head];
jj_[i] = j, xxi[i] = f(i, j);
x_ = max(x_, xxi[i]);
}
build();
if (n <= 200) {
for (i = 0; i < n; i++)
for (j = i + k; j <= n; j++)
if (f(i, j) == x_) {
s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
update_(i, j - 1, y_);
}
} else {
for (j = k; j <= n; j++)
if (xxj[j] == x_) {
i = ii_[j];
s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
update_(i, j - 1, y_);
}
for (i = 0; i <= n - k; i++)
if (xxi[i] == x_) {
j = jj_[i];
s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
update_(i, j - 1, y_);
}
}
for (i = 1; i < n_; i++)
st[i << 1 | 0] = min(st[i << 1 | 0], st[i]), st[i << 1 | 1] = min(st[i << 1 | 1], st[i]);
for (i = 0; i < n; i++)
cc[i] = st[n_ + i] <= yy[i] ? '1' : '0';
printf("%lld\n", x_);
printf("%s\n", cc);
return 0;
}
Compilation message
trade.c: In function 'main':
trade.c:133:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
trade.c:135:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
| ^~~~~~~~~~~~~~~~~~~~~
trade.c:137:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d", &yy[i]);
| ^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12636 KB |
Output is correct |
3 |
Correct |
2 ms |
12784 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
12812 KB |
Output is correct |
7 |
Correct |
1 ms |
12636 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
12636 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12636 KB |
Output is correct |
3 |
Correct |
2 ms |
12784 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
12812 KB |
Output is correct |
7 |
Correct |
1 ms |
12636 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
12636 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
12636 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
2 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
19 |
Correct |
1 ms |
12636 KB |
Output is correct |
20 |
Correct |
1 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
12636 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
2 ms |
13660 KB |
Output is correct |
24 |
Correct |
17 ms |
14428 KB |
Output is correct |
25 |
Correct |
16 ms |
14320 KB |
Output is correct |
26 |
Correct |
16 ms |
14464 KB |
Output is correct |
27 |
Correct |
3 ms |
13148 KB |
Output is correct |
28 |
Correct |
9 ms |
13660 KB |
Output is correct |
29 |
Correct |
6 ms |
14240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12632 KB |
Output is correct |
2 |
Correct |
120 ms |
33620 KB |
Output is correct |
3 |
Correct |
367 ms |
51284 KB |
Output is correct |
4 |
Correct |
1318 ms |
108336 KB |
Output is correct |
5 |
Partially correct |
1343 ms |
107636 KB |
Partially correct |
6 |
Correct |
1376 ms |
106652 KB |
Output is correct |
7 |
Correct |
960 ms |
103344 KB |
Output is correct |
8 |
Correct |
477 ms |
58964 KB |
Output is correct |
9 |
Correct |
442 ms |
54084 KB |
Output is correct |
10 |
Correct |
290 ms |
50768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12632 KB |
Output is correct |
2 |
Correct |
120 ms |
33620 KB |
Output is correct |
3 |
Correct |
367 ms |
51284 KB |
Output is correct |
4 |
Correct |
1318 ms |
108336 KB |
Output is correct |
5 |
Partially correct |
1343 ms |
107636 KB |
Partially correct |
6 |
Correct |
1376 ms |
106652 KB |
Output is correct |
7 |
Correct |
960 ms |
103344 KB |
Output is correct |
8 |
Correct |
477 ms |
58964 KB |
Output is correct |
9 |
Correct |
442 ms |
54084 KB |
Output is correct |
10 |
Correct |
290 ms |
50768 KB |
Output is correct |
11 |
Correct |
1 ms |
12632 KB |
Output is correct |
12 |
Correct |
125 ms |
32852 KB |
Output is correct |
13 |
Correct |
352 ms |
50004 KB |
Output is correct |
14 |
Correct |
1348 ms |
108372 KB |
Output is correct |
15 |
Partially correct |
1347 ms |
107604 KB |
Partially correct |
16 |
Correct |
1360 ms |
106416 KB |
Output is correct |
17 |
Correct |
968 ms |
103108 KB |
Output is correct |
18 |
Correct |
469 ms |
58984 KB |
Output is correct |
19 |
Correct |
456 ms |
54216 KB |
Output is correct |
20 |
Correct |
292 ms |
50004 KB |
Output is correct |
21 |
Correct |
1 ms |
12636 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
1 ms |
12636 KB |
Output is correct |
24 |
Correct |
1 ms |
12636 KB |
Output is correct |
25 |
Correct |
2 ms |
12636 KB |
Output is correct |
26 |
Correct |
1 ms |
12636 KB |
Output is correct |
27 |
Correct |
1 ms |
12636 KB |
Output is correct |
28 |
Correct |
1 ms |
12720 KB |
Output is correct |
29 |
Correct |
1 ms |
12636 KB |
Output is correct |
30 |
Correct |
1 ms |
12636 KB |
Output is correct |
31 |
Correct |
329 ms |
50208 KB |
Output is correct |
32 |
Partially correct |
1312 ms |
107588 KB |
Partially correct |
33 |
Correct |
1397 ms |
106604 KB |
Output is correct |
34 |
Correct |
1313 ms |
93888 KB |
Output is correct |
35 |
Correct |
1199 ms |
96420 KB |
Output is correct |
36 |
Correct |
549 ms |
60496 KB |
Output is correct |
37 |
Correct |
170 ms |
35152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12636 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
2 ms |
12784 KB |
Output is correct |
6 |
Correct |
1 ms |
12636 KB |
Output is correct |
7 |
Correct |
1 ms |
12636 KB |
Output is correct |
8 |
Correct |
2 ms |
12812 KB |
Output is correct |
9 |
Correct |
1 ms |
12636 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
12636 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
1 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
19 |
Correct |
2 ms |
12636 KB |
Output is correct |
20 |
Correct |
1 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
12636 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
1 ms |
12636 KB |
Output is correct |
24 |
Correct |
1 ms |
12636 KB |
Output is correct |
25 |
Correct |
2 ms |
13660 KB |
Output is correct |
26 |
Correct |
17 ms |
14428 KB |
Output is correct |
27 |
Correct |
16 ms |
14320 KB |
Output is correct |
28 |
Correct |
16 ms |
14464 KB |
Output is correct |
29 |
Correct |
3 ms |
13148 KB |
Output is correct |
30 |
Correct |
9 ms |
13660 KB |
Output is correct |
31 |
Correct |
6 ms |
14240 KB |
Output is correct |
32 |
Correct |
1 ms |
12632 KB |
Output is correct |
33 |
Correct |
120 ms |
33620 KB |
Output is correct |
34 |
Correct |
367 ms |
51284 KB |
Output is correct |
35 |
Correct |
1318 ms |
108336 KB |
Output is correct |
36 |
Partially correct |
1343 ms |
107636 KB |
Partially correct |
37 |
Correct |
1376 ms |
106652 KB |
Output is correct |
38 |
Correct |
960 ms |
103344 KB |
Output is correct |
39 |
Correct |
477 ms |
58964 KB |
Output is correct |
40 |
Correct |
442 ms |
54084 KB |
Output is correct |
41 |
Correct |
290 ms |
50768 KB |
Output is correct |
42 |
Correct |
1 ms |
12632 KB |
Output is correct |
43 |
Correct |
125 ms |
32852 KB |
Output is correct |
44 |
Correct |
352 ms |
50004 KB |
Output is correct |
45 |
Correct |
1348 ms |
108372 KB |
Output is correct |
46 |
Partially correct |
1347 ms |
107604 KB |
Partially correct |
47 |
Correct |
1360 ms |
106416 KB |
Output is correct |
48 |
Correct |
968 ms |
103108 KB |
Output is correct |
49 |
Correct |
469 ms |
58984 KB |
Output is correct |
50 |
Correct |
456 ms |
54216 KB |
Output is correct |
51 |
Correct |
292 ms |
50004 KB |
Output is correct |
52 |
Correct |
1 ms |
12636 KB |
Output is correct |
53 |
Correct |
1 ms |
12636 KB |
Output is correct |
54 |
Correct |
1 ms |
12636 KB |
Output is correct |
55 |
Correct |
1 ms |
12636 KB |
Output is correct |
56 |
Correct |
2 ms |
12636 KB |
Output is correct |
57 |
Correct |
1 ms |
12636 KB |
Output is correct |
58 |
Correct |
1 ms |
12636 KB |
Output is correct |
59 |
Correct |
1 ms |
12720 KB |
Output is correct |
60 |
Correct |
1 ms |
12636 KB |
Output is correct |
61 |
Correct |
1 ms |
12636 KB |
Output is correct |
62 |
Correct |
329 ms |
50208 KB |
Output is correct |
63 |
Partially correct |
1312 ms |
107588 KB |
Partially correct |
64 |
Correct |
1397 ms |
106604 KB |
Output is correct |
65 |
Correct |
1313 ms |
93888 KB |
Output is correct |
66 |
Correct |
1199 ms |
96420 KB |
Output is correct |
67 |
Correct |
549 ms |
60496 KB |
Output is correct |
68 |
Correct |
170 ms |
35152 KB |
Output is correct |
69 |
Correct |
1 ms |
12636 KB |
Output is correct |
70 |
Correct |
132 ms |
32988 KB |
Output is correct |
71 |
Correct |
356 ms |
50088 KB |
Output is correct |
72 |
Correct |
1319 ms |
108208 KB |
Output is correct |
73 |
Partially correct |
1340 ms |
107644 KB |
Partially correct |
74 |
Correct |
1377 ms |
106576 KB |
Output is correct |
75 |
Correct |
916 ms |
103216 KB |
Output is correct |
76 |
Correct |
480 ms |
59124 KB |
Output is correct |
77 |
Correct |
434 ms |
54068 KB |
Output is correct |
78 |
Correct |
299 ms |
50004 KB |
Output is correct |
79 |
Correct |
1 ms |
12636 KB |
Output is correct |
80 |
Correct |
1 ms |
12636 KB |
Output is correct |
81 |
Correct |
1 ms |
12636 KB |
Output is correct |
82 |
Correct |
1 ms |
12636 KB |
Output is correct |
83 |
Correct |
2 ms |
12636 KB |
Output is correct |
84 |
Correct |
1 ms |
12636 KB |
Output is correct |
85 |
Correct |
1 ms |
12636 KB |
Output is correct |
86 |
Correct |
1 ms |
12636 KB |
Output is correct |
87 |
Correct |
1 ms |
12636 KB |
Output is correct |
88 |
Correct |
1 ms |
12636 KB |
Output is correct |
89 |
Correct |
326 ms |
50240 KB |
Output is correct |
90 |
Partially correct |
1314 ms |
107644 KB |
Partially correct |
91 |
Correct |
1389 ms |
106600 KB |
Output is correct |
92 |
Correct |
1326 ms |
93968 KB |
Output is correct |
93 |
Correct |
1196 ms |
96260 KB |
Output is correct |
94 |
Correct |
550 ms |
60680 KB |
Output is correct |
95 |
Correct |
165 ms |
33872 KB |
Output is correct |
96 |
Correct |
2 ms |
13660 KB |
Output is correct |
97 |
Correct |
16 ms |
14428 KB |
Output is correct |
98 |
Correct |
16 ms |
14428 KB |
Output is correct |
99 |
Correct |
17 ms |
14396 KB |
Output is correct |
100 |
Correct |
3 ms |
13144 KB |
Output is correct |
101 |
Correct |
9 ms |
13660 KB |
Output is correct |
102 |
Correct |
6 ms |
14172 KB |
Output is correct |
103 |
Correct |
2069 ms |
104860 KB |
Output is correct |
104 |
Correct |
1389 ms |
96772 KB |
Output is correct |
105 |
Correct |
1338 ms |
93108 KB |
Output is correct |
106 |
Partially correct |
1134 ms |
93360 KB |
Partially correct |
107 |
Correct |
121 ms |
92560 KB |
Output is correct |
108 |
Correct |
599 ms |
94172 KB |
Output is correct |
109 |
Correct |
91 ms |
34988 KB |
Output is correct |
110 |
Correct |
268 ms |
57168 KB |
Output is correct |
111 |
Correct |
698 ms |
105564 KB |
Output is correct |
112 |
Partially correct |
143 ms |
35152 KB |
Partially correct |