#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct ST{
vector<ll> a;
vector<bool> b;
int n;
ST(int ns){
n = ns;
a.resize(n + 1);
b.resize(n + 1);
}
void upd(int p, ll x){
a[p] = x;
b[p] = 1;
}
void add(int l, int r, int x){
for (int i = l; i <= r; i++){
a[i] += x;
}
}
ll get1(int p){
return a[p];
}
int get2(int p){
int sum = 0;
for (int i = 1; i <= p; i++) sum += b[i];
return sum;
}
};
struct ST1{
vector<ll> a;
int n;
ST1(int ns){
n = ns;
a.resize(n + 1);
}
void upd(int p, ll x){
a[p] = x;
}
void add(int l, int r, ll x){
for (int i = l; i <= r; i++){
a[i] += x;
}
}
ll get(){
ll out = 0;
for (int i = 1; i <= n; i++){
out = max(out, a[i]);
}
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout<<fixed<<setprecision(15);
auto print = [&](ll x){
if (x % 2 == 0){
cout<<x / 2<<" ";
}
else {
cout<<(x - 1) / 2<<".5 ";
}
};
int n, m, d; cin>>n>>m>>d;
vector<int> a(n + 1), b(m + 1);
vector<pii> all = {{0, 0}};
for (int i = 1; i <= n; i++){
cin>>a[i];
all.pb({a[i], i});
}
for (int i = 1; i <= m; i++){
cin>>b[i];
all.pb({b[i], i + n});
}
sort(all.begin(), all.end());
vector<int> p(all.size());
for (int i = 1; i < all.size(); i++) p[all[i].ss] = i;
// f[i] = x[i] - d * i
// t[i] = x[j] - x[i] + d * (i - j)
int N = (int) all.size() - 1;
ST T(N); ST1 T1(N);
int cc = 0;
vector<int> r(N + 1);
set<int> st;
auto add = [&](int x){
cc++;
int i = p[cc];
ll vi = x - 1LL * d * (T.get2(i) + 1);
T.upd(i, vi);
T.add(i + 1, N, -d);
auto it = st.lower_bound(i);
if (it != st.begin()){
int j = *prev(it);
ll vj = T.get1(j);
T1.add(i + 1, N, d);
T1.add(max(i, r[j]) + 1, N, -d);
while (true){
auto it1 = st.upper_bound(j);
if (it1 == st.end()) break;
int k = *it1;
if (T.get1(k) <= vj){
r[j] = r[k];
T1.add(k, r[k], all[j].ff - all[k].ff + 1LL * d * (T.get2(k) - T.get2(j)));
st.erase(it1);
continue;
}
break;
}
if (vj >= vi){
T1.upd(i, all[j].ff - x + 1LL * d * (T.get2(i) - T.get2(j)));
r[j] = max(r[j], i);
return;
}
T1.add(i + 1, r[j], x - all[j].ff);
r[i] = r[j];
r[j] = i - 1;
}
T1.upd(i, 0);
r[i] = max(r[i], i);
while (true){
it = st.lower_bound(i);
if (it == st.end()) break;
int k = *it;
if (T.get1(k) <= vi){
r[i] = r[k];
T1.add(k, r[k], x - all[k].ff + 1LL * d * (T.get2(k) - T.get2(i)));
st.erase(it);
continue;
}
break;
}
st.insert(i);
};
for (int i = 1; i <= n; i++){
add(a[i]);
}
for (int i = 1; i <= m; i++){
add(b[i]);
print(T1.get());
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 1; i < all.size(); i++) p[all[i].ss] = i;
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1540 ms |
8128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1540 ms |
8128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
