#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int MAXN = 4e5 + 5;
const ll INF = 1e15;
struct Node {
ll mini, maks, diff, lazy;
Node(ll mini, ll maks, ll diff, ll lazy) :
mini(mini), maks(maks), diff(diff), lazy(lazy) {}
Node() : mini(INF), maks(-INF), diff(-INF), lazy(0) {}
};
class Tournament {
int offset;
vector <Node> tour;
public:
Tournament(int n) {
for (offset = 1; offset < n; offset *= 2);
tour.resize(2 * offset);
}
Node merge(Node lhs, Node rhs) {
return Node(min(lhs.mini, rhs.mini), max(lhs.maks, rhs.maks), max(max(lhs.diff, rhs.diff), rhs.maks - lhs.mini), 0);
}
void prop(int x) {
tour[x].mini += tour[x].lazy;
tour[x].maks += tour[x].lazy;
if (x < offset) {
tour[2 * x].lazy += tour[x].lazy;
tour[2 * x + 1].lazy += tour[x].lazy;
}
tour[x].lazy = 0;
}
void refresh(int x) {
tour[x] = merge(tour[2 * x], tour[2 * x + 1]);
}
void update(int x, int lo, int hi, int from, int to, int val) {
prop(x);
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
tour[x].lazy += val;
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(2 * x, lo, mid, from, to, val);
update(2 * x + 1, mid, hi, from, to, val);
refresh(x);
}
void update(int x, int val) {
update(1, 0, offset, x, offset, val);
}
void modify(int x, int lo, int hi, int pos, int val) {
prop(x);
if (lo > pos || hi <= pos)
return;
if (hi - lo == 1) {
tour[x].mini += val - INF;
tour[x].maks += val + INF;
return;
}
int mid = (lo + hi) / 2;
modify(2 * x, lo, mid, pos, val);
modify(2 * x + 1, mid, hi, pos, val);
refresh(x);
}
void modify(int x, int val) {
modify(1, 0, offset, x, val);
}
ll get() {
prop(1);
return max(tour[1].diff, 0ll);
}
};
int N, M, D;
int pos[MAXN];
pii p[MAXN];
void load() {
scanf("%d%d%d", &N, &M, &D);
for (int i = 0; i < N + M; i++) {
scanf("%d", &p[i].first);
p[i].second = i;
}
}
void solve() {
sort(p, p + N + M);
for (int i = 0; i < N + M; i++)
pos[p[i].second] = i;
Tournament solver(N + M);
for (int i = 0; i < N + M; i++) {
solver.modify(pos[i], -p[pos[i]].first);
solver.update(pos[i], D);
ll ans = solver.get();
if (i >= N)
printf("%lld%s", ans / 2, ans % 2 ? ".5 " : " ");
}
puts("");
}
int main() {
load();
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void load()':
Main.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d%d", &N, &M, &D);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &p[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
448 KB |
Output is correct |
6 |
Correct |
2 ms |
472 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
448 KB |
Output is correct |
6 |
Correct |
2 ms |
472 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
225 ms |
20392 KB |
Output is correct |
10 |
Correct |
216 ms |
20628 KB |
Output is correct |
11 |
Correct |
152 ms |
19756 KB |
Output is correct |
12 |
Correct |
167 ms |
20192 KB |
Output is correct |
13 |
Correct |
149 ms |
19828 KB |
Output is correct |
14 |
Correct |
157 ms |
19908 KB |
Output is correct |
15 |
Correct |
209 ms |
19888 KB |
Output is correct |
16 |
Correct |
147 ms |
19288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
175 ms |
21144 KB |
Output is correct |
2 |
Correct |
173 ms |
23204 KB |
Output is correct |
3 |
Correct |
173 ms |
22776 KB |
Output is correct |
4 |
Correct |
171 ms |
20544 KB |
Output is correct |
5 |
Correct |
171 ms |
22368 KB |
Output is correct |
6 |
Correct |
170 ms |
21168 KB |
Output is correct |
7 |
Correct |
170 ms |
22660 KB |
Output is correct |
8 |
Correct |
166 ms |
21580 KB |
Output is correct |
9 |
Correct |
174 ms |
20836 KB |
Output is correct |
10 |
Correct |
175 ms |
23000 KB |
Output is correct |
11 |
Correct |
172 ms |
21652 KB |
Output is correct |
12 |
Correct |
174 ms |
22800 KB |
Output is correct |
13 |
Correct |
170 ms |
20556 KB |
Output is correct |
14 |
Correct |
172 ms |
23000 KB |
Output is correct |
15 |
Correct |
177 ms |
21816 KB |
Output is correct |
16 |
Correct |
165 ms |
20916 KB |
Output is correct |
17 |
Correct |
172 ms |
22392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
175 ms |
21144 KB |
Output is correct |
2 |
Correct |
173 ms |
23204 KB |
Output is correct |
3 |
Correct |
173 ms |
22776 KB |
Output is correct |
4 |
Correct |
171 ms |
20544 KB |
Output is correct |
5 |
Correct |
171 ms |
22368 KB |
Output is correct |
6 |
Correct |
170 ms |
21168 KB |
Output is correct |
7 |
Correct |
170 ms |
22660 KB |
Output is correct |
8 |
Correct |
166 ms |
21580 KB |
Output is correct |
9 |
Correct |
174 ms |
20836 KB |
Output is correct |
10 |
Correct |
175 ms |
23000 KB |
Output is correct |
11 |
Correct |
172 ms |
21652 KB |
Output is correct |
12 |
Correct |
174 ms |
22800 KB |
Output is correct |
13 |
Correct |
170 ms |
20556 KB |
Output is correct |
14 |
Correct |
172 ms |
23000 KB |
Output is correct |
15 |
Correct |
177 ms |
21816 KB |
Output is correct |
16 |
Correct |
165 ms |
20916 KB |
Output is correct |
17 |
Correct |
172 ms |
22392 KB |
Output is correct |
18 |
Correct |
234 ms |
20512 KB |
Output is correct |
19 |
Correct |
245 ms |
22964 KB |
Output is correct |
20 |
Correct |
178 ms |
23164 KB |
Output is correct |
21 |
Correct |
194 ms |
21500 KB |
Output is correct |
22 |
Correct |
207 ms |
21572 KB |
Output is correct |
23 |
Correct |
180 ms |
21216 KB |
Output is correct |
24 |
Correct |
237 ms |
21628 KB |
Output is correct |
25 |
Correct |
170 ms |
21308 KB |
Output is correct |
26 |
Correct |
229 ms |
21188 KB |
Output is correct |
27 |
Correct |
242 ms |
23320 KB |
Output is correct |
28 |
Correct |
205 ms |
21828 KB |
Output is correct |
29 |
Correct |
230 ms |
21708 KB |
Output is correct |
30 |
Correct |
193 ms |
20496 KB |
Output is correct |
31 |
Correct |
192 ms |
22760 KB |
Output is correct |
32 |
Correct |
183 ms |
21848 KB |
Output is correct |
33 |
Correct |
276 ms |
19952 KB |
Output is correct |
34 |
Correct |
191 ms |
21132 KB |
Output is correct |