#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
ll pos[200005];
ll val[200005];
struct node {
ll mn, mx, lz, ans;
};
node tree[200005 * 4];
void sett(int x, int l, int r, int p, int v) {
if (l == r) {
tree[x].mn = tree[x].mx = v + tree[x].lz;
tree[x].ans = 0;
return;
}
int mid = (l + r) / 2;
if (p <= mid) sett(2 * x, l, mid, p, v);
else sett(2 * x + 1, mid + 1, r, p, v);
tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}
void add(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
tree[x].lz += v;
tree[x].mx += v;
tree[x].mn += v;
return;
}
if (l > qr || ql > r) return;
int mid = (l + r) / 2;
add(2 * x, l, mid, ql, qr, v);
add(2 * x + 1, mid + 1, r, ql, qr, v);
tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}
void build(int x, int l, int r) {
tree[x].mn = 1e15;
tree[x].mx = -1e15;
tree[x].ans = -1e15;
if (l == r) {
return;
}
int mid = (l + r) / 2;
build(2 * x, l, mid);
build(2 * x + 1, mid + 1, r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, m, d; cin >> n >> m >> d;
build(1, 1, 200000);
vector<pair<ll, ll>> v;
for (int i = 1; i <= n + m; i++) {
int t; cin >> t;
val[i] = t;
v.push_back({t, i});
}
sort(v.begin(), v.end());
for (int i = 1; i <= n + m; i++) {
pos[v[i - 1].second] = i;
}
for (int i = 1; i <= n; i++) {
sett(1, 1, 200000, pos[i], val[i]);
add(1, 1, 200000, pos[i] + 1, 200000, -d);
}
for (int i = n + 1; i <= n + m; i++) {
sett(1, 1, 200000, pos[i], val[i]);
add(1, 1, 200000, pos[i] + 1, 200000, -d);
ll res = tree[1].ans;
if (res % 2 == 1) {
cout << res / 2 << ".5 ";
} else cout << res / 2 << " " ;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16852 KB |
Output is correct |
2 |
Correct |
9 ms |
16852 KB |
Output is correct |
3 |
Correct |
9 ms |
16768 KB |
Output is correct |
4 |
Correct |
9 ms |
16824 KB |
Output is correct |
5 |
Correct |
8 ms |
16844 KB |
Output is correct |
6 |
Correct |
9 ms |
16852 KB |
Output is correct |
7 |
Correct |
9 ms |
16852 KB |
Output is correct |
8 |
Correct |
9 ms |
16856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16852 KB |
Output is correct |
2 |
Correct |
9 ms |
16852 KB |
Output is correct |
3 |
Correct |
9 ms |
16768 KB |
Output is correct |
4 |
Correct |
9 ms |
16824 KB |
Output is correct |
5 |
Correct |
8 ms |
16844 KB |
Output is correct |
6 |
Correct |
9 ms |
16852 KB |
Output is correct |
7 |
Correct |
9 ms |
16852 KB |
Output is correct |
8 |
Correct |
9 ms |
16856 KB |
Output is correct |
9 |
Runtime error |
168 ms |
41872 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
120 ms |
24108 KB |
Output is correct |
2 |
Correct |
121 ms |
25996 KB |
Output is correct |
3 |
Correct |
142 ms |
27216 KB |
Output is correct |
4 |
Correct |
116 ms |
24816 KB |
Output is correct |
5 |
Correct |
133 ms |
26648 KB |
Output is correct |
6 |
Correct |
122 ms |
25608 KB |
Output is correct |
7 |
Correct |
122 ms |
26896 KB |
Output is correct |
8 |
Correct |
122 ms |
25852 KB |
Output is correct |
9 |
Correct |
128 ms |
25288 KB |
Output is correct |
10 |
Correct |
124 ms |
27732 KB |
Output is correct |
11 |
Correct |
121 ms |
25948 KB |
Output is correct |
12 |
Correct |
123 ms |
27144 KB |
Output is correct |
13 |
Correct |
114 ms |
25160 KB |
Output is correct |
14 |
Correct |
120 ms |
27268 KB |
Output is correct |
15 |
Correct |
123 ms |
26832 KB |
Output is correct |
16 |
Correct |
112 ms |
25052 KB |
Output is correct |
17 |
Correct |
123 ms |
26588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
120 ms |
24108 KB |
Output is correct |
2 |
Correct |
121 ms |
25996 KB |
Output is correct |
3 |
Correct |
142 ms |
27216 KB |
Output is correct |
4 |
Correct |
116 ms |
24816 KB |
Output is correct |
5 |
Correct |
133 ms |
26648 KB |
Output is correct |
6 |
Correct |
122 ms |
25608 KB |
Output is correct |
7 |
Correct |
122 ms |
26896 KB |
Output is correct |
8 |
Correct |
122 ms |
25852 KB |
Output is correct |
9 |
Correct |
128 ms |
25288 KB |
Output is correct |
10 |
Correct |
124 ms |
27732 KB |
Output is correct |
11 |
Correct |
121 ms |
25948 KB |
Output is correct |
12 |
Correct |
123 ms |
27144 KB |
Output is correct |
13 |
Correct |
114 ms |
25160 KB |
Output is correct |
14 |
Correct |
120 ms |
27268 KB |
Output is correct |
15 |
Correct |
123 ms |
26832 KB |
Output is correct |
16 |
Correct |
112 ms |
25052 KB |
Output is correct |
17 |
Correct |
123 ms |
26588 KB |
Output is correct |
18 |
Correct |
175 ms |
26004 KB |
Output is correct |
19 |
Correct |
190 ms |
27300 KB |
Output is correct |
20 |
Correct |
157 ms |
27672 KB |
Output is correct |
21 |
Correct |
147 ms |
25544 KB |
Output is correct |
22 |
Correct |
151 ms |
26012 KB |
Output is correct |
23 |
Correct |
125 ms |
25764 KB |
Output is correct |
24 |
Correct |
178 ms |
26292 KB |
Output is correct |
25 |
Correct |
138 ms |
25728 KB |
Output is correct |
26 |
Correct |
167 ms |
25388 KB |
Output is correct |
27 |
Correct |
173 ms |
27424 KB |
Output is correct |
28 |
Correct |
151 ms |
26052 KB |
Output is correct |
29 |
Correct |
189 ms |
25996 KB |
Output is correct |
30 |
Correct |
146 ms |
24976 KB |
Output is correct |
31 |
Correct |
156 ms |
27256 KB |
Output is correct |
32 |
Correct |
128 ms |
26380 KB |
Output is correct |
33 |
Correct |
167 ms |
24092 KB |
Output is correct |
34 |
Correct |
151 ms |
26308 KB |
Output is correct |