#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(51);
#define ll long long
#define pb push_back
#define ld long double
const int N = 4e5 + 10;
int n, m, d;
struct Fenwick {
vector<ll> t;
Fenwick(int n) {
t.resize(n);
}
void inc(int i, int d) {
for (; i < t.size(); i = (i | (i + 1))) {
t[i] += d;
}
}
ll get(int r) {
ll ans = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) {
ans += t[r];
}
return ans;
}
ll get(ll l, ll r) {
return get(r) - get(l - 1);
}
} pr(N), sf(N);
struct SegTree {
vector<int> t;
SegTree(int n) {
t.resize(4 * n);
}
void update(int v, int l, int r, int pos, int val) {
if (l == r) {
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) {
update(2 * v, l, m, pos, val);
} else {
update(2 * v + 1, m + 1, r, pos, val);
}
t[v] = t[v * 2] + t[v * 2 + 1];
}
int get_ind(int v, int l, int r, int val) {
if (l == r) {
return l;
}
int m = (l + r) / 2;
if (t[v * 2] >= val) {
return get_ind(2 * v, l, m, val);
} else {
return get_ind(2 * v + 1, m + 1, r, val - t[v * 2]);
}
}
} t(N);
set<pair<int,int>> st;
vector<pair<int,int>> u;
void update_pr(auto it, int x) {
if (it == st.begin()) return;
auto pre = prev(it);
int pos = lower_bound(u.begin(), u.end(), *it) - u.begin();
pr.inc(pos, x * max(0, d - (it->first - pre->first)));
}
void update_sf(auto it, int x) {
if (next(it) == st.end()) return;
auto nxt = next(it);
int pos = lower_bound(u.begin(), u.end(), *it) - u.begin();
sf.inc(pos, x * max(0, d - (nxt->first - it->first)));
}
ld get_val(int num) {
int pos = t.get_ind(1, 0, N - 1, num);
return (ld)max(pr.get(0, pos), sf.get(pos, N - 1));
}
ld get_pair_val(int num) {
int pos1 = t.get_ind(1, 0, N - 1, num), pos2 = t.get_ind(1, 0, N - 1, num + 1);
return (ld)max(pr.get(0, pos1), sf.get(pos2, N - 1)) + (ld)max(0, d - (u[pos2].first - u[pos1].first)) / 2.0;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
int cnt = 0, kol = 0;
cin >> n >> m >> d;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
u.pb({a[i], kol});
st.insert({a[i], kol++});
}
for (int i = 0; i < m; i++) {
cin >> b[i];
u.pb({b[i], kol++});
}
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
int sz = u.size();
for (auto it = st.begin(); it != st.end(); it = next(it)) {
update_pr(it, 1);
update_sf(it, 1);
}
for (int i = 0; i < n; i++) {
int pos = lower_bound(u.begin(), u.end(), make_pair(a[i], cnt)) - u.begin();
t.update(1, 0, N - 1, pos, 1);
cnt++;
}
for (int i = 0; i < m; i++) {
auto up = st.upper_bound({b[i], cnt});
if (up != st.end() && up != st.begin()) {
update_pr(up, -1);
update_sf(prev(up), -1);
}
st.insert({b[i], cnt});
auto it = st.lower_bound({b[i], cnt});
update_pr(it, 1);
update_sf(it, 1);
if (next(it) != st.end()) {
update_pr(next(it), 1);
}
if (it != st.begin()) {
update_sf(prev(it), 1);
}
int pos = lower_bound(u.begin(), u.end(), make_pair(b[i], cnt)) - u.begin();
t.update(1, 0, N - 1, pos, 1);
ld ans = 1e18;
for (int j = 1; j <= st.size(); j++) {
ans = min(ans, get_val(j));
}
for (int j = 1; j + 1 <= st.size(); j++) {
ans = min(ans, get_pair_val(j));
}
/*int l = 0, r = st.size();
while (r - l > 2) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (get_val(m1) > get_val(m2)) {
l = m1;
} else {
r = m2;
}
}
for (auto a : {l, l + 1, l + 2}) {
if (1 <= a && a <= st.size()) {
ans = min(ans, get_val(a));
}
}
l = 0, r = st.size();
while (r - l > 2) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (get_pair_val(m1) > get_pair_val(m2)) {
l = m1;
} else {
r = m2;
}
}
for (auto a : {l, l + 1, l + 2}) {
if (1 <= a && a + 1 <= st.size()) {
ans = min(ans, get_pair_val(a));
}
}*/
cout << ans << ' ';
cnt++;
}
return 0;
}
Compilation message
Main.cpp: In member function 'void Fenwick::inc(int, int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (; i < t.size(); i = (i | (i + 1))) {
| ~~^~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:70:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
70 | void update_pr(auto it, int x) {
| ^~~~
Main.cpp:77:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
77 | void update_sf(auto it, int x) {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:143:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int j = 1; j <= st.size(); j++) {
| ~~^~~~~~~~~~~~
Main.cpp:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int j = 1; j + 1 <= st.size(); j++) {
| ~~~~~~^~~~~~~~~~~~
Main.cpp:114:9: warning: unused variable 'sz' [-Wunused-variable]
114 | int sz = u.size();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
15796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
15796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
