This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 3);
int n, m, d;
int a[250005];
int pos[250005];
vector< pair<int, int> > v;
pair<ll, ll> t[2*OFF+5];
ll p[2*OFF+5];
void prop(int x) {
if (p[x] == 0 || x >= OFF) return;
t[x*2].X += p[x];
t[x*2+1].X += p[x];
t[x*2].Y += p[x];
t[x*2+1].Y += p[x];
p[x*2] += p[x];
p[x*2+1] += p[x];
p[x] = 0;
return;
}
ll query(int a, int b, int l, int r, int x) {
if (r <= a || b <= l) {
if (a == 0) return -INF;
return INF;
}
if (a <= l && r <= b) {
if (a == 0) return t[x].Y;
return t[x].X;
}
prop(x);
ll o1 = query(a, b, l, (l+r)/2, x*2);
ll o2 = query(a, b, (l+r)/2, r, x*2+1);
//cout << o1 << " " << o2 << endl;
if (a == 0) return max(o1, o2);
return min(o1, o2);
}
void update(int a, int b, int l, int r, int x, ll kol) {
if (r <= a || b <= l) return;
if (a <= l && r <= b) {
if (kol == INF+1) {
t[x].X += -INF;
t[x].Y += INF;
return;
}
t[x].X += kol;
t[x].Y += kol;
p[x] += kol;
return;
}
prop(x);
update(a, b, l, (l+r)/2, x*2, kol);
update(a, b, (l+r)/2, r, x*2+1, kol);
t[x].X = min(t[x*2].X, t[x*2+1].X);
t[x].Y = max(t[x*2].Y, t[x*2+1].Y);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> d;
for (int i = 0; i < n; i++) {
cin >> a[i];
v.push_back({a[i], i});
}
for (int i = n; i < n+m; i++) {
cin >> a[i];
v.push_back({a[i], i});
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
pos[v[i].Y] = i;
}
for (int i = OFF+n+m-1; i > 0; i--) {
t[i].X = INF;
t[i].Y = -INF;
}
ll sol = 0;
int najl = 1e9, najr = -1e9;
for (int i = 0; i < n+m; i++) {
update(pos[i], pos[i]+1, 0, OFF, 1, INF+1);
update(pos[i], pos[i]+1, 0, OFF, 1, a[i]);
update(pos[i]+1, n+m, 0, OFF, 1, -d);
ll lo = query(0, pos[i]+1, 0, OFF, 1);
ll hi = query(pos[i], n+m, 0, OFF, 1);
//cout << i << ": " << lo << " " << hi << " " << pos[i] << " " << query(pos[i], pos[i]+1, 0, OFF, 1) << endl;
if (najl == 1e9 && najr == -1e9) {
najl = pos[i];
najr = pos[i];
}
else if (pos[i] >= najl || pos[i] <= najr) sol = max(sol, -hi+lo);
else if (pos[i] > najr) {
sol = max(sol, (ll)pos[i]*(ll)d-a[i]+lo);
najr = pos[i];
}
else if (pos[i] < najl) {
sol = max(sol, -hi+a[i]-(ll)pos[i]*(ll)d);
najl = pos[i];
}
if (i >= n) {
cout << sol/2;
if (sol % 2 == 1) cout << ".5";
cout << " ";
}
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
# | 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... |