Submission #701338

#	Time	Username	Problem	Language	Result	Execution time	Memory
701338		PurpleCrayon	Measures (CEOI22_measures)	C++17	100 / 100	436 ms	43256 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+20, MOD = 998244353;
const ll INF = 1e18+10;

#include <bits/extc++.h>
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct T {
    ll max_active, min_active, ans, lazy;

    T() {
        max_active = -INF;
        min_active = INF;
        ans = lazy = 0;
    }

    T(ll x) {
        max_active = min_active = x;
        ans = lazy = 0;
    }

    friend T operator + (const T& a, const T& b) {
        T ret = T();
        ret.max_active = max(a.max_active, b.max_active);
        ret.min_active = min(a.min_active, b.min_active);
        ret.ans = max({a.ans, b.ans, b.max_active - a.min_active});

        return ret;
    }
};

vector<T> t;

void push(int v, int tl, int tr, ll x) {
    t[v].max_active += x;
    t[v].min_active += x;

    if (tl != tr)
        t[2*v].lazy += x, t[2*v+1].lazy += x;
}

void app(int v, int tl, int tr) {
    push(v, tl, tr, t[v].lazy);
    t[v].lazy = 0;
}

void upd(int v, int tl, int tr, int l, int r, ll x) {
    app(v, tl, tr);
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        push(v, tl, tr, x);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
    t[v] = t[2*v] + t[2*v+1];
}

void activate(int v, int tl, int tr, int i, ll x) {
    app(v, tl, tr);
    if (i < tl || i > tr) return;
    if (tl == tr) {
        t[v] = T(x);
        return;
    }

    int tm = (tl + tr) / 2;
    activate(2*v, tl, tm, i, x), activate(2*v+1, tm+1, tr, i, x);
    t[v] = t[2*v] + t[2*v+1];
}

void solve() {
    int n, m, d; cin >> n >> m >> d;
    vector<int> a(n); for (auto& x : a) cin >> x;
    vector<int> b(m); for (auto& x : b) cin >> x;

    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        v.emplace_back(a[i], i);
    }
    for (int i = 0; i < m; i++) {
        v.emplace_back(b[i], n + i);
    }

    sort(v.begin(), v.end());

    vector<int> loc_a(n), loc_b(m);
    for (int i = 0; i < n + m; i++) {
        if (v[i].second < n) {
            loc_a[v[i].second] = i;
        } else {
            loc_b[v[i].second - n] = i;
        }
    }

    oset<int> s;
    t.assign(4 * (n + m), T());

    auto add = [&](int i, ll x) {
        activate(1, 0, n + m - 1, i, (long long) d * s.order_of_key(i) - x);
        s.insert(i);

        upd(1, 0, n + m - 1, i + 1, n + m - 1, d);
    };


    for (int i = 0; i < n; i++) {
        add(loc_a[i], a[i]);
    }

    for (int i = 0; i < m; i++) {
        add(loc_b[i], b[i]);

        app(1, 0, n + m - 1);
        ll ans = t[1].ans;
        cout << ans / 2;
        if (ans % 2) cout << ".5";
        cout << ' ';
    }
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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