#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int mxN = 1e6 + 5;
ll n,a[mxN],b[mxN],d,n1,m,idx[mxN];
map<ll,ll> idx1;
set<ll> ss;
struct segtree{
vector<ll> v,p,s,cnt;
ll sz = 1;
void init(){
while(sz < n) sz *= 2;
v.assign(2 * sz, 0LL);
p.assign(2 * sz, -1e10);
s.assign(2 * sz, -1e10);
cnt.assign(2 * sz, 0LL);
}
void set(ll i, ll x, ll lx, ll rx){
if(rx - lx == 1){
s[x] = -idx[min(i + 1, n - 1)] + idx[i] + cnt[x] * d;
p[x] = cnt[x] * d;
v[x] = cnt[x] * d;
cnt[x]++;
// if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
return;
}
ll mid = lx + (rx - lx) / 2;
if(i < mid) set(i, 2 * x + 1, lx, mid);
else set(i, 2 * x + 2, mid, rx);
cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
v[x] = max(v[2 * x + 1] , v[2 * x + 2]);
s[x] = s[2 * x + 2];
p[x] = p[2 * x + 1];
if(cnt[2 * x + 1] and cnt[2 * x + 2]) v[x] = max(v[x], d + s[2 * x + 1] + p[2 * x + 2]);
p[x] = max(p[x], p[2 * x + 2] - (idx[mid] - idx[lx]) + cnt[2 * x + 1] * d);
s[x] = max(s[x], s[2 * x + 1] - (idx[min(rx, n - 1)] - idx[mid]) + cnt[2 * x + 2] * d);
// if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
}
void set(ll i){
set(i, 0, 0, sz);
}
ll find(){
return v[0];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n1 >> m >> d;
for(int i = 0; i < n1; i++){
cin >> a[i];
ss.insert(a[i]);
}
for(int i = 0; i < m; i++){
cin >> b[i];
ss.insert(b[i]);
}
ll cc = 0;
for(auto it : ss){
idx1[it] = cc;
idx[cc++] = it;
}
// idx[cc] = 2e9;
n = ss.size();
segtree s;
s.init();
vector<ll> vv;
for(int i = 0; i < n1; i++){
s.set(idx1[a[i]]);
vv.pb(a[i]);
// cout << a[i] << ' ' << idx1[a[i]] << ' ' << s.find() << '\n';
}
for(int i = 0; i < m; i++){
s.set(idx1[b[i]]);
vv.pb(b[i]);
sort(vv.begin(), vv.end());
ll ans = 0;
for(int j = 1; j < vv.size(); j++){
ll x = 0;
for(int k = j - 1; k >= 0; k--){
x += d;
ans = max(ans, x - vv[j] + vv[k]);
}
}
assert(ans == s.find());
cout << (double)s.find() / 2 << ' ';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int j = 1; j < vv.size(); j++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
4976 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
4976 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1544 ms |
45224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1544 ms |
45224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
