Submission #683322

#	Time	Username	Problem	Language	Result	Execution time	Memory
683322		nutella	Measures (CEOI22_measures)	C++17	100 / 100	426 ms	25008 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll inf = 3e18;

struct Info {
    ll mx = 0, a = inf, b = -inf; //min_a, max_b

    Info() = default;
    Info(ll a, ll b) : a(a), b(b), mx(b - a) {}
    Info(ll mx, ll a, ll b) : a(a), b(b), mx(mx) {}
};

Info operator+(Info x, Info y) {
    return {max({x.mx, y.mx, y.b - x.a}), min(x.a, y.a), max(x.b, y.b)};
}

vector<Info> t;
vector<ll> tag;
int sz = 1;

void init(int n) {
    sz = 1 << __lg(n) + bool(n & (n - 1));
    t.resize(sz << 1), tag.resize(sz << 1);
}

void apply(Info &a, ll tg) {
    a.a += tg, a.b += tg;
}

void apply(int x, ll tg) {
    apply(t[x], tg);
    tag[x] += tg;
}

void push(int x) {
    apply(x << 1, tag[x]), apply(x << 1 | 1, tag[x]);
    tag[x] = 0;
}

void pull(int x) {
    t[x] = t[x << 1] + t[x << 1 | 1];
}

void rangeAdd(int l, int r, ll D, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) {
        return;
    }
    if (l <= lx && rx <= r) {
        apply(x, D);
        return;
    }
    push(x);

    int mid = (lx + rx) >> 1;
    rangeAdd(l, r, D, x << 1, lx, mid), rangeAdd(l, r, D, x << 1 | 1, mid, rx);

    pull(x);
}

void modify(int i, Info b, int x = 1, int lx = 0, int rx = sz) {
    if (lx + 1 == rx) {
        t[x] = b;
        return;
    }
    push(x);

    int mid = (lx + rx) >> 1;
    if (i < mid) {
        modify(i, b, x << 1, lx, mid);
    } else {
        modify(i, b, x << 1 | 1, mid, rx);
    }

    pull(x);
}

struct Fenwick {
    vector<int> t;
    int n{};

    void init(int m) {
        n = m;
        t.resize(n + 1);
    }

    void modify(int i, int v) {
        for (int x = i + 1; x <= n; x += x & -x) {
            t[x] += v;
        }
    }

    int sum(int i) {
        int ans = 0;
        for (int x = i + 1; x > 0; x -= x & -x) {
            ans += t[x];
        }
        return ans;
    }
};

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

    int n, m, D;
    cin >> n >> m >> D;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> b(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    if (n > 0) {
        sort(a.begin(), a.end());

        for (int i = 0; i < m; ++i) {
            a.insert(lower_bound(a.begin(), a.end(), b[i]), b[i]);


            ll ans = numeric_limits<ll>::min(), mx = numeric_limits<ll>::min();
            for (int k = size(a) - 1; k >= 0; --k) {
                mx = max(mx, 1LL * D * k - a[k]);

                ans = max(ans, mx - 1LL * D * k + a[k]);
            }

            if (ans % 2 == 0) {
                cout << ans / 2 << ' ';
            } else {
                cout << ans / 2 << ".5 ";
            }
        }
    } else {
        init(m);

        vector<pair<int, int>> yy(m);
        for (int i = 0; i < m; ++i) {
            yy[i] = {b[i], i};
        }
        sort(yy.begin(), yy.end());

        Fenwick fn;
        fn.init(m);

        for (int i = 0; i < m; ++i) {
            int pos = lower_bound(yy.begin(), yy.end(), pair{b[i], i}) - yy.begin();

            rangeAdd(pos + 1, m, D);

            ll val = 1LL * D * fn.sum(pos - 1);
            Info now = Info(val - b[i], val - b[i]);

            modify(pos, now);
            fn.modify(pos, 1);

            if (t[1].mx % 2 == 0) {
                cout << t[1].mx / 2 << " ";
            } else {
                cout << t[1].mx / 2 << ".5 ";
            }
        }
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'Info::Info(ll, ll)':
Main.cpp:9:25: warning: 'Info::b' will be initialized after [-Wreorder]
    9 |     ll mx = 0, a = inf, b = -inf; //min_a, max_b
      |                         ^
Main.cpp:9:8: warning:   'll Info::mx' [-Wreorder]
    9 |     ll mx = 0, a = inf, b = -inf; //min_a, max_b
      |        ^~
Main.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     Info(ll a, ll b) : a(a), b(b), mx(b - a) {}
      |     ^~~~
Main.cpp: In constructor 'Info::Info(ll, ll, ll)':
Main.cpp:9:25: warning: 'Info::b' will be initialized after [-Wreorder]
    9 |     ll mx = 0, a = inf, b = -inf; //min_a, max_b
      |                         ^
Main.cpp:9:8: warning:   'll Info::mx' [-Wreorder]
    9 |     ll mx = 0, a = inf, b = -inf; //min_a, max_b
      |        ^~
Main.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     Info(ll mx, ll a, ll b) : a(a), b(b), mx(mx) {}
      |     ^~~~
Main.cpp: In function 'void init(int)':
Main.cpp:25:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |     sz = 1 << __lg(n) + bool(n & (n - 1));
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41