#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
struct IT {
vector<ll> hi, lo, lazy;
IT (int sz) : hi(4 * sz), lo(4 * sz), lazy(4 * sz) {}
ll addLo (ll a, ll b) {
return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MAX : a + b);
}
ll addHi (ll a, ll b) {
return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MIN : a + b);
}
ll getHi (int k) { return addHi(hi[k], lazy[k]); }
ll getLo (int k) { return addLo(lo[k], lazy[k]); }
void refine (int k) {
hi[k] = max(getHi(2 * k), getHi(2 * k + 1));
lo[k] = min(getLo(2 * k), getLo(2 * k + 1));
}
void pushDown (int k) {
if (!lazy[k]) return;
lazy[2 * k] = addHi(lazy[2 * k], lazy[k]), lazy[2 * k + 1] = addHi(lazy[2 * k + 1], lazy[k]);
lazy[k] = 0, refine(k);
}
void update (int a, int b, ll incr, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
lazy[k] = addHi(lazy[k], incr);
return;
}
pushDown(k);
int mid = (l + r) >> 1;
update(a, b, incr, 2 * k, l, mid);
update(a, b, incr, 2 * k + 1, mid + 1, r);
refine(k);
}
ll query (int a, int b, int k, int l, int r) {
if (b < l || r < a) return LLONG_MIN;
if (a <= l && r <= b) return getHi(k);
pushDown(k);
int mid = (l + r) >> 1;
return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
}
int walk (ll targ, int k, int l, int r) {
if (l == r) return l;
pushDown(k);
int mid = (l + r) >> 1;
if (getLo(2 * k) < targ) return walk(targ, 2 * k, l, mid);
return walk(targ, 2 * k + 1, mid + 1, r);
}
int findID (int a, int b, ll targ, int k, int l, int r) {
if (b < l || r < a) return INT_MAX;
if (a <= l && r <= b)
return (getLo(k) < targ ? walk(targ, k, l, r) : INT_MAX);
pushDown(k);
int mid = (l + r) >> 1;
int cur = findID(a, b, targ, 2 * k, l, mid);
return (cur < INT_MAX ? cur : findID(a, b, targ, 2 * k + 1, mid + 1, r));
}
ll access (int pos, int k, int l, int r) {
if (l == r) return getLo(k);
int mid = (l + r) >> 1;
if (pos <= mid)
return addLo(lazy[k], access(pos, 2 * k, l, mid));
return addLo(lazy[k], access(pos, 2 * k + 1, mid + 1, r));
}
void build (vector<ll> &a, int k, int l, int r) {
if (l == r) {
hi[k] = lo[k] = a[l];
return;
}
int mid = (l + r) >> 1;
build(a, 2 * k, l, mid);
build(a, 2 * k + 1, mid + 1, r);
refine(k);
}
};
const int mn = 2e5 + 50;
int st[mn], nxt[mn], prv[mn];
bool ok (vector<pl> vec, ll D, ll mov) {
ll last = LLONG_MIN;
for (pl it : vec) {
ll init = it.first, cur = max(init - mov, last + D);
if (cur > init + mov) return 0;
last = cur;
}
return 1;
}
ll solve (vector<pl> vec, ll D) {
if (ok(vec, D, 0)) return 0;
ll ans = 0;
for (ll msk = (1LL << 60); msk > 0; msk >>= 1)
if (!ok(vec, D, ans | msk)) ans |= msk;
return ans + 1;
}
int getInt() {
int num = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
num = (num << 3) + (num << 1) + (ch - '0');
ch = getchar();
}
return num;
}
int main()
{
freopen("MEASURES.inp", "r", stdin);
freopen("MEASURES.out", "w", stdout);
int n = getInt(), m = getInt(), D = 2 * getInt();
vector<pl> vec(n + m);
for (int i = 0; i < n + m; i++) {
st[i] = 2 * getInt();
vec[i] = {st[i], i}, nxt[i] = i + 1, prv[i] = i - 1;
}
prv[n + m] = n + m - 1;
sort(all(vec));
ll curAns = solve(vec, D), last = LLONG_MIN;
function<int(int)> getID = [&] (int initID) {
return lower_bound(all(vec), make_pair((ll)st[initID], (ll)initID)) - vec.begin();
};
vector<ll> a(n + m);
for (int i = 0; i < n + m; i++) {
ll init = vec[i].first, cur = max(init - curAns, last + D);
a[i] = cur - init, last = cur;
}
IT tree(n + m); tree.build(a, 1, 0, n + m - 1);
vector<ll> ans;
for (int i = n + m - 1; i >= n; i--) {
ans.push_back(curAns);
int cur = getID(i);
tree.update(cur, cur, LLONG_MIN, 1, 0, n + m - 1);
if (prv[cur] >= 0) nxt[prv[cur]] = nxt[cur];
prv[nxt[cur]] = prv[cur];
if (nxt[cur] < n + m) {
int tmp = nxt[cur];
while (tmp < n + m) {
ll goCur = tree.access(tmp, 1, 0, n + m - 1), pos = vec[tmp].first + goCur;
ll gap = goCur + curAns;
if (prv[tmp] >= 0) {
ll posL = vec[prv[tmp]].first + tree.access(prv[tmp], 1, 0, n + m - 1);
gap = min(gap, pos - posL - D);
}
if (!gap) break;
int bound = prv[min(n + m, tree.findID(tmp, n + m - 1, goCur, 1, 0, n + m - 1))];
tree.update(tmp, bound, -gap, 1, 0, n + m - 1);
tmp = nxt[bound];
}
}
/*cout << "curAns " << curAns << ": ";
for (int j = 0; j < n + m; j++) {
ll br = tree.query(j, j, 1, 0, n + m - 1);
if (br < -100) cout << "inf ";
else cout << br << " ";
}
cout << endl;*/
ll decrAns = min(curAns, (curAns - tree.getHi(1)) / 2LL);
tree.update(0, n + m - 1, decrAns, 1, 0, n + m - 1);
curAns -= decrAns;
}
reverse(all(ans));
for (ll u : ans) {
printf("%lld", u / 2);
if (u % 2) printf(".5");
printf(" ");
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:138:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen("MEASURES.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:139:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | freopen("MEASURES.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1523 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1523 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1511 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1511 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
