Submission #1111961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111961		MisterReaper	Measures (CEOI22_measures)	C++17	100 / 100	258 ms	22344 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "../../debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 INF = i64(1E18);
constexpr int max_N = int(2E5) + 100;

i64 ans = 0;
int N, M, D, n;

#define def int mid = (l + r) >> 1, lv = (v << 1), rv = (v << 1 | 1);
struct node {
    i64 mx, mn, lazy;
    node() {}
    node(i64 mx_, i64 mn_, i64 lazy_) {
        mx = mx_;
        mn = mn_;
        lazy = lazy_;
    }
    void modify(i64 x) {
        mx += x;
        mn += x;
        lazy += x;
    }
} tree[max_N << 2];
node unite(const node& lhs, const node& rhs) {
    return node{std::max(lhs.mx, rhs.mx), std::min(lhs.mn, rhs.mn), 0};
}
void build(int v, int l, int r) {
    if (l == r) {
        tree[v] = node{-INF, INF, 0};
        return;
    }
    def;
    build(lv, l, mid);
    build(rv, mid + 1, r);
    tree[v] = unite(tree[lv], tree[rv]);
}
void build() {
    build(1, 0, n - 1);
}
void push(int v, int l, int r) {
    def;
    tree[lv].modify(tree[v].lazy);
    tree[rv].modify(tree[v].lazy);
    tree[v].lazy = 0;
}
void modify(int v, int l, int r, int ql, int qr, i64 x) {
    if (ql == l && r == qr) {
        tree[v].modify(x);
        return;
    }
    push(v, l, r);
    def;
    if (qr <= mid) {
        modify(lv, l, mid, ql, qr, x);
    } else if (mid + 1 <= ql) {
        modify(rv, mid + 1, r, ql, qr, x);
    } else {
        modify(lv, l, mid, ql, mid, x);
        modify(rv, mid + 1, r, mid + 1, qr, x);
    }
    tree[v] = unite(tree[lv], tree[rv]);
}
void modify(int l, int r, i64 x) {
    modify(1, 0, n - 1, l, r, x);
}
void set(int v, int l, int r, int p, node x) {
    if (l == r) {
        tree[v] = x;
        return;
    }
    push(v, l, r);
    def;
    if (p <= mid) {
        set(lv, l, mid, p, x);
    } else {
        set(rv, mid + 1, r, p, x);
    }
    tree[v] = unite(tree[lv], tree[rv]);
}
void set(int p, node x) {
    set(1, 0, n - 1, p, x);
}
node query(int v, int l, int r, int ql, int qr) {
    if (ql == l && r == qr) {
        return node{tree[v].mx, tree[v].mn, 0};
    }
    push(v, l, r);
    def;
    if (qr <= mid) {
        return query(lv, l, mid, ql, qr);
    } else if (mid + 1 <= ql) {
        return query(rv, mid + 1, r, ql, qr);
    } else {
        auto ansl = query(lv, l, mid, ql, mid);
        auto ansr = query(rv, mid + 1, r, mid + 1, qr);
        return unite(ansl, ansr);
    }
}
node query(int l, int r) {
    return query(1, 0, n - 1, l, r);
}
void debug_segtree(int v, int l, int r) {
    if (l != r) push(v, l, r);
    debug(v, l, r, tree[v].mx, tree[v].mn);
    if (l == r) {
        return;
    }
    def;
    debug_segtree(lv, l, mid);
    debug_segtree(rv, mid + 1, r);
}
void debug_segtree() {
    #ifdef DEBUG
        debug_segtree(1, 0, n - 1);
    #endif
}

int ft[max_N];
int lsb(int x) {
    return x & -x;
}
void fen_modify(int p, int x) {
    for (p += 1; p <= n; p += lsb(p)) {
        ft[p] += x;
    }
}
int fen_query(int p) {
    int res = 0;
    for (p += 1; p; p -= lsb(p)) {
        res += ft[p];
    }
    return res;
}

void add(int x, int p) {
    if (p != n - 1) {
        modify(p + 1, n - 1, D);
    }
    i64 val = i64(fen_query(p)) * D - x;
    fen_modify(p, +1);
    set(p, node{val, val, 0});
    auto lhs = query(0, p);
    auto rhs = query(p, n - 1);
    debug(x, p, val, lhs.mn, rhs.mx);
    ans = std::max({ans, rhs.mx - lhs.mn});
    debug_segtree();
}

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

    std::cin >> N >> M >> D;
    n = N + M;
    std::vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> A[i];
    }

    std::vector<int> ord(n), inv_ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return A[lhs] < A[rhs];
    });
    for (int i = 0; i < n; ++i) {
        inv_ord[ord[i]] = i;
    }

    build();

    debug_segtree();
    for (int i = 0; i < n; ++i) {
        add(A[i], inv_ord[i]);
        if (i >= N) {
            if (ans % 2 == 0) {
                std::cout << ans / 2 << '\n';
            } else {
                std::cout << ans / 2 << ".5\n";
            }
        }
        debug(ans);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void push(int, int, int)':
Main.cpp:17:17: warning: unused variable 'mid' [-Wunused-variable]
   17 | #define def int mid = (l + r) >> 1, lv = (v << 1), rv = (v << 1 | 1);
      |                 ^~~
Main.cpp:49:5: note: in expansion of macro 'def'
   49 |     def;
      |     ^~~

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