/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n, m, pos[N], co[N];
ll D, T[N][2], lazy[N][2];
void build(int l, int r, int k){
lazy[k][0] = lazy[k][1] = 0;
co[k] = 0;
if(l == r){
T[k][0] = -1e18;
T[k][1] = 1e18;
co[k] = 0;
return;
}
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
T[k][0] = -1e18;
T[k][1] = 1e18;
}
void push(int k){
for(int r = 0; r < 2; ++r){
lazy[k<<1][r] += lazy[k][r];
lazy[k<<1|1][r] += lazy[k][r];
T[k<<1][r] += lazy[k][r];
T[k<<1|1][r] += lazy[k][r];
lazy[k][r] = 0;
}
}
void sett(int l, int r, int p, int k, ll val){
if(l == r){
T[k][0] = val;
T[k][1] = val;
co[k] = 1;
return;
}
push(k);
int mid = l+r>>1;
if(p <= mid)
sett(l, mid, p, k<<1, val);
else
sett(mid+1, r, p, k<<1|1, val);
T[k][0] = max(T[k<<1][0], T[k<<1|1][0]);
T[k][1] = min(T[k<<1][1], T[k<<1|1][1]);
co[k] = co[k<<1] + co[k<<1|1];
}
void update(int l, int r, int ql, int qr, int k, ll add){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
T[k][0] += add;
T[k][1] += add;
lazy[k][0] += add;
lazy[k][1] += add;
return;
}
push(k);
int mid = l+r>>1;
update(l, mid, ql, qr, k<<1, add);
update(mid+1, r, ql, qr, k<<1|1, add);
T[k][0] = max(T[k<<1][0], T[k<<1|1][0]);
T[k][1] = min(T[k<<1][1], T[k<<1|1][1]);
co[k] = co[k<<1] + co[k<<1|1];
}
pair<ll, ll> get(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return {(ll)-1e18, (ll)1e18};
if(ql <= l && r <= qr) return {T[k][0], T[k][1]};
push(k);
int mid = l+r>>1;
auto v1 = get(l, mid, ql, qr, k<<1);
auto v2 = get(mid+1, r, ql, qr, k<<1|1);
return {max(v1.first, v2.first), min(v1.second, v2.second)};
}
int sum(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return 0;
if(ql <= l && r <= qr) return co[k];
push(k);
int mid = l+r>>1;
return sum(l, mid, ql, qr, k<<1) + sum(mid+1, r, ql, qr, k<<1|1);
}
void solve(){
cin >> n >> m >> D;
for(int i = 0; i < n; ++i){
int x; cin >> x;
}
vector<array<ll, 2>> v;
for(int i = 0; i < m; ++i){
ll x; cin >> x;
v.pb({x, i});
}
sort(all(v));
for(int i = 0; i < m; ++i) pos[v[i][1]] = i;
set<int> active;
build(1, m, 1);
ll ans = 0;
for(int i = 0; i < m; ++i){
ll cur = v[pos[i]][0];
int P = pos[i];
auto it = active.lower_bound(P);
int l, r;
if(it == active.begin()) l = -1;
else l = *prev(it);
if(it == active.end()) r = -1;
else r = *it;
if(P < m)
update(1, m, P + 1, m, 1, D);
ll val = (sum(1, m, 1, P, 1) + 1) * D - cur;
if(l != -1){
ll L = get(1, m, 1, l, 1).second;
ans = max(ans, val - L);
}
if(r != -1){
ll R = get(1, m, r, m, 1).first;
ans = max(ans, R - val);
}
sett(1, m, P, 1, val);
active.insert(P);
if(ans % 2 == 0) cout << ans / 2 << ' ';
else cout << ans/2 << ".5" << ' ';
// for(auto k: active) cout << k << ' ';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = l+r>>1;
| ~^~
Main.cpp: In function 'void sett(int, int, int, int, long long int)':
Main.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = l+r>>1;
| ~^~
Main.cpp: In function 'void update(int, int, int, int, int, long long int)':
Main.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l+r>>1;
| ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, int, int)':
Main.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = l+r>>1;
| ~^~
Main.cpp: In function 'int sum(int, int, int, int, int)':
Main.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = l+r>>1;
| ~^~
Main.cpp: In function 'int main()':
Main.cpp:138:15: warning: unused variable 'aa' [-Wunused-variable]
138 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
40704 KB |
Output is correct |
| 2 |
Incorrect |
235 ms |
42688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
40704 KB |
Output is correct |
| 2 |
Incorrect |
235 ms |
42688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
