Submission #634368

#	Time	Username	Problem	Language	Result	Execution time	Memory
634368		Ooops_sorry	Measures (CEOI22_measures)	C++17	100 / 100	493 ms	53732 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int N = 2e5 + 100;
const ll INF = 1e18;

struct node {
    ll ans, mx, mn;
    node() {
        ans = 0, mx = -INF, mn = INF;
    }
    node(ll ans_, ll mx_, ll mn_) {
        ans = ans_, mx = mx_, mn = mn_;
    }
};

struct SegTree {
    vector<ll> add;
    vector<node> t;
    SegTree(int n) {
        t.resize(4 * n);
        add.resize(4 * n, 0);
    }
    void inc(int v, ll val) {
        t[v].mn += val;
        t[v].mx += val;
        add[v] += val;
    }
    void push(int v) {
        inc(v * 2, add[v]);
        inc(v * 2 + 1, add[v]);
        add[v] = 0;
    }
    void upd(int v) {
        node a = t[v * 2], b = t[v * 2 + 1], res;
        res.ans = max({a.ans, b.ans, b.mx - a.mn});
        res.mn = min(a.mn, b.mn);
        res.mx = max(a.mx, b.mx);
        t[v] = res;
    }
    void update_pos(int v, int l, int r, int pos, ll val) {
        if (l == r) {
            t[v].mn = t[v].mx = val;
            return;
        }
        push(v);
        int m = (l + r) / 2;
        if (pos <= m) {
            update_pos(2 * v, l, m, pos, val);
        } else {
            update_pos(2 * v + 1, m + 1, r, pos, val);
        }
        upd(v);
    }
    void update(int v, int tl, int  tr, int l, int r, ll val) {
        if (l > r) return;
        if (tl == l && tr == r) {
            inc(v, val);
            return;
        }
        push(v);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, min(r, tm), val), update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
        upd(v);
    }
};

struct Fenwick {
    vector<int> t;
    Fenwick(int n) {
        t.resize(n);
    }
    void inc(int i, int d) {
        for (; i < t.size(); i = (i | (i + 1))) {
            t[i] += d;
        }
    }
    int get(int r) {
        int ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += t[r];
        }
        return ans;
    }
};

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> a(n), b(m), u;
    map<int, vector<int>> pos;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        u.pb(a[i]);
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        u.pb(b[i]);
    }
    sort(u.begin(), u.end());
    int sz = u.size();
    for (int i = 0; i < sz; i++) {
        pos[u[i]].pb(i);
    }
    SegTree t(sz);
    Fenwick f(sz);
    auto add = [&](int a) -> int {
        int ind = pos[a].back();
        pos[a].pop_back();
        t.update(1, 0, sz - 1, ind + 1, sz - 1, d);
        t.update_pos(1, 0, sz - 1, ind, (ll)f.get(ind) * d - u[ind]);
        f.inc(ind, 1);
        return 0;
    };
    for (int i = 0; i < n; i++) {
        add(a[i]);
    }
    for (int i = 0; i < m; i++) {
        add(b[i]);
        cout << t.t[1].ans / 2;
        if (t.t[1].ans % 2 == 1) {
            cout << ".5";
        }
        cout << ' ';
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Fenwick::inc(int, int)':
Main.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (; i < t.size(); i = (i | (i + 1))) {
      |                ~~^~~~~~~~~~

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