#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int M = 8 * N;
int n, m, d, a[N], b[N], ord[N], pos[N];
struct LazySegmentTree {
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll mx[M], lzy[M];
void push(int x) {
if ((x << 1 | 1) >= M) {
return;
}
mx[x << 1] += lzy[x];
mx[x << 1 | 1] += lzy[x];
lzy[x << 1] += lzy[x];
lzy[x << 1 | 1] += lzy[x];
lzy[x] = 0;
}
void pull(int x) {
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
void init(int x, int l, int r) {
mx[x] = -inf;
if (l == r) return;
int mid = l + r >> 1;
init(x << 1, l, mid);
init(x << 1 | 1, mid + 1, r);
}
void inc(int x, int l, int r, int ql, int qr, ll v) {
if (l > r || l > qr || r < ql || ql > qr) {
return;
}
if (ql <= l && r <= qr) {
mx[x] += v;
lzy[x] += v;
return;
}
push(x);
int mid = l + r >> 1;
inc(x << 1, l, mid, ql, qr, v);
inc(x << 1 | 1, mid + 1, r, ql, qr, v);
pull(x);
}
void upd(int x, int l, int r, int p, ll v) {
push(x);
if (l == r) {
mx[x] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid) {
upd(x << 1, l, mid, p, v);
} else {
upd(x << 1 | 1, mid + 1, r, p, v);
}
pull(x);
}
ll query(int x, int l, int r, int ql, int qr) {
if (l > r || l > qr || r < ql || ql > qr) {
return -inf;
}
if (ql <= l && r <= qr) {
return mx[x];
}
push(x);
int mid = l + r >> 1;
ll lx = query(x << 1, l, mid, ql, qr);
ll rx = query(x << 1 | 1, mid + 1, r, ql, qr);
pull(x);
return max(lx, rx);
}
} L, R;
struct Fenwick {
int c[N];
void init() {
for (int i = 0; i < N; i++) c[i] = 0;
}
void modify(int p, int x) {
for (; p < N; p += p & -p) c[p] += x;
}
int query(int p) {
int s = 0;
for (; p > 0; p -= p & -p) s += c[p];
return s;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
} fenw;
int main() {
scanf("%d%d%d", &n, &m, &d);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
ord[i] = i;
}
sort(ord + 1, ord + m + 1, [&](int i, int j) { return b[i] < b[j]; } );
for (int i = 1; i <= m; i++) {
pos[ord[i]] = i;
}
L.init(1, 1, m);
R.init(1, 1, m);
fenw.init();
ll ans = 0;
for (int i = 1; i <= m; i++) {
fenw.modify(pos[i], +1);
L.upd(1, 1, m, i, -fenw.query(pos[i]) * 1ll * d + b[i]);
R.upd(1, 1, m, i, +fenw.query(pos[i]) * 1ll * d - b[i]);
R.inc(1, 1, m, pos[i] + 1, m, +d);
ans = max(ans, L.query(1, 1, m, 1, pos[i]) + R.query(1, 1, m, pos[i] + 1, m));
ans = max(ans, L.query(1, 1, m, 1, pos[i] - 1) + R.query(1, 1, m, pos[i], m));
if (ans & 1) {
printf("%lld.5 ", ans / 2);
} else {
printf("%lld " , ans / 2);
}
}
return 0;
}
Compilation message
Main.cpp: In member function 'void LazySegmentTree::init(int, int, int)':
Main.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void LazySegmentTree::inc(int, int, int, int, int, long long int)':
Main.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void LazySegmentTree::upd(int, int, int, int, long long int)':
Main.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'long long int LazySegmentTree::query(int, int, int, int, int)':
Main.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d%d%d", &n, &m, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d", &b[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
37664 KB |
Output is correct |
| 2 |
Incorrect |
247 ms |
41568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
37664 KB |
Output is correct |
| 2 |
Incorrect |
247 ms |
41568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
