이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 4e5 + 5;
int n, m, a[N], D, tmp;
ll seg[2][N << 2], lz[2][N << 2];
int fen[N];
bool mark[N];
void upd_fen(int i) {
for (++i; i <= tmp + 2; i += i & -i)
fen[i]++;
}
int query_fen(int i) {
int res = 0;
for (++i; i > 0; i -= i & -i)
res += fen[i];
return res;
}
void shift(int t, int v, int tl, int tr) {
seg[t][v] += lz[t][v];
if (tl < tr) {
lz[t][v << 1] += lz[t][v];
lz[t][v << 1 | 1] += lz[t][v];
}
lz[t][v] = 0;
}
void upd(int t, int l, int r, ll val, int v = 1, int tl = 0, int tr = tmp) {
shift(t, v, tl, tr);
if (l > tr || r < tl)
return;
if (tl >= l && tr <= r) {
lz[t][v] += val;
shift(t, v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
upd(t, l, r, val, v << 1, tl, mid);
upd(t, l, r, val, v << 1 | 1, mid + 1, tr);
if (t) {
seg[t][v] = min(seg[t][v << 1], seg[t][v << 1 | 1]);
}
else {
seg[t][v] = max(seg[t][v << 1], seg[t][v << 1 | 1]);
}
}
ll query(int t, int l, int r, int v = 1, int tl = 0, int tr = tmp) {
shift(t, v, tl, tr);
if (l > tr || r < tl) {
return t ? 1e17 : -1e17;
}
if (tl >= l && tr <= r)
return seg[t][v];
int mid = (tl + tr) >> 1;
ll lc = query(t, l, r, v << 1, tl, mid), rc = query(t, l, r, v << 1 | 1, mid + 1, tr);
if (t)
return min(lc, rc);
return max(lc, rc);
}
void solve() {
cin >> n >> m >> D;
ll ans = 0;
vector<pair<int, int> > vec;
for (int i = 0; i < n; i++) {
cin >> a[i];
vec.pb(mp(a[i], tmp));
tmp++;
}
for (int i = 0; i < m; i++) {
cin >> a[tmp];
vec.pb(mp(a[tmp], tmp));
tmp++;
}
sort(vec.begin(), vec.end());
fill(seg[0], seg[0] + (N << 2), -1e17);
fill(seg[1], seg[1] + (N << 2), 1e17);
for (int i = 0; i < tmp; i++) {
int j = lower_bound(vec.begin(), vec.end(), mp(a[i], i)) - vec.begin();
mark[j] = true;
ll x = 1LL * D * query_fen(j) - a[i];
upd_fen(j);
upd(0, j + 1, tmp, D);
upd(1, j + 1, tmp, D);
upd(0, j, j, x - query(0, j, j));
upd(1, j, j, x - query(1, j, j));
//ans = max(ans, query(0, j, tmp) - query(1, 0, j));
if (i >= n) {
ans = 0;
for (int j = 0; j < tmp; j++)
ans = max(ans, query(0, j, tmp) - query(1, 0, j));
cout << ans / 2;
if (ans % 2)
cout << ".5";
if (i < tmp - 1)
cout << ' ';
}
}
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |