Submission #1330357

#TimeUsernameProblemLanguageResultExecution timeMemory
1330357shirokuma5Measures (CEOI22_measures)C++20
0 / 100
357 ms21224 KiB
/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)

template<class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b; return 1;
    }
    return 0;
}
template<class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b; return 1;
    }
    return 0;
}
struct edge {
    int to, w;
};
ll inv(ll a) {
    ll b = mod, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= b * t;
        swap(a, b);
        u -= v * t;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
template<class T> void print(vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
    return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
    T x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
    return (bit < (1LL << N));
}
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

struct Node {
    ll maxi, mini;
};
Node op(Node a, Node b) {
    return {max(a.maxi, b.maxi), min(a.mini, b.mini)};
}
Node e() {
    return {-INF, INF};
}
Node mapping(ll f, Node a) {
    ll aa = a.maxi + f, bb = a.mini + f;
    if (a.maxi == -INF) aa = -INF;
    if (a.mini == INF) bb = INF;
    return {aa, bb};
}
ll composition(ll f, ll g) {
    return f + g;
}
ll id() { return 0; }
class LazySegmentTree {
    public:
    int siz = 1, h = 0;
    vector<Node> dat;
    vector<ll> lazy;

    void init(int n) {
        while (siz <= n) {siz *= 2; h++;}
        dat.assign(siz * 2, e()); lazy.assign(siz * 2, id());
    }

    void eval(int u) {
        if (lazy[u] != id()) {
            dat[u] = mapping(lazy[u], dat[u]);
            if (u < siz) {
                lazy[u * 2] = composition(lazy[u * 2], lazy[u]);
                lazy[u * 2 + 1] = composition(lazy[u * 2 + 1], lazy[u]);
            }
            lazy[u] = id();
        }
    }

    void apply(int l, int r, ll x, int a = 0, int b = -1, int u = 1) {
        if (b == -1) b = siz;
        eval(u);
        if (r <= a || b <= l) return;
        if (l <= a && b <= r) {
            lazy[u] = composition(lazy[u], x); eval(u); return;
        }
        int m = (a + b) / 2;
        apply(l, r, x, a, m, u * 2); apply(l, r, x, m, b, u * 2 + 1);
        dat[u] = op(dat[u * 2], dat[u * 2 + 1]);
    }

    Node prod(int l, int r, int a = 0, int b = -1, int u = 1) {
        if (b == -1) b = siz;
        eval(u);
        if (r <= a || b <= l) return e();
        if (l <= a && b <= r) return dat[u];
        int m = (a + b) / 2;
        return op(prod(l, r, a, m, u * 2), prod(l, r, m, b, u * 2 + 1));
    }

    void set(int pos, ll x) {
        pos += siz;
        eval(1);
        repd(i, h) {
            eval((pos >> (i + 1)) * 2);
            eval((pos >> (i + 1)) * 2 + 1);
        }
        dat[pos] = {x, x};
        while (pos >= 2) {
            pos /= 2; dat[pos] = op(dat[pos * 2], dat[pos * 2 + 1]);
        }

    }


};

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m; cin >> n >> m; ll d; cin >> d;
    vector<ll> a(n), b(m), rev(n + m);
    vector<pair<ll, ll>> people; people.reserve(n + m);
    rep(i, n) {
        cin >> a[i]; people.push_back({a[i], i});
    }
    rep(i, m) {
        cin >> b[i]; people.push_back({b[i], i + n});
    }
    sort(people.begin(), people.end());
    rep(i, n + m) rev[people[i].second] = i;
    LazySegmentTree Z; Z.init(n + m);
    ll res = 0;

    rep(i, m) {
        Z.apply(rev[i + n] + 1, Z.siz, -d);
        Z.set(rev[i + n], b[i] - d * (i + n));
        chmax(res, Z.prod(0, rev[i+n]+1).maxi - Z.prod(rev[i+n], Z.siz).mini);
        cout << (long double)res / 2 << endl;
    }


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...