oj.uz

Submission #701338

# Submission time Handle Problem Language Result Execution time Memory
701338 2023-02-21T01:58:14 Z PurpleCrayon Measures (CEOI22_measures) C++17
100 / 100
 436 ms 43256 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 429 ms 37776 KB Output is correct
10 Correct 343 ms 39748 KB Output is correct
11 Correct 295 ms 39996 KB Output is correct
12 Correct 261 ms 39804 KB Output is correct
13 Correct 290 ms 39380 KB Output is correct
14 Correct 276 ms 39748 KB Output is correct
15 Correct 384 ms 39100 KB Output is correct
16 Correct 287 ms 39772 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 38920 KB Output is correct
2 Correct 335 ms 42792 KB Output is correct
3 Correct 327 ms 42688 KB Output is correct
4 Correct 318 ms 40628 KB Output is correct
5 Correct 320 ms 41796 KB Output is correct
6 Correct 327 ms 40900 KB Output is correct
7 Correct 329 ms 41936 KB Output is correct
8 Correct 320 ms 40636 KB Output is correct
9 Correct 329 ms 40516 KB Output is correct
10 Correct 324 ms 42948 KB Output is correct
11 Correct 331 ms 41412 KB Output is correct
12 Correct 320 ms 42292 KB Output is correct
13 Correct 328 ms 40704 KB Output is correct
14 Correct 321 ms 42580 KB Output is correct
15 Correct 336 ms 42392 KB Output is correct
16 Correct 321 ms 40132 KB Output is correct
17 Correct 325 ms 41920 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 38920 KB Output is correct
2 Correct 335 ms 42792 KB Output is correct
3 Correct 327 ms 42688 KB Output is correct
4 Correct 318 ms 40628 KB Output is correct
5 Correct 320 ms 41796 KB Output is correct
6 Correct 327 ms 40900 KB Output is correct
7 Correct 329 ms 41936 KB Output is correct
8 Correct 320 ms 40636 KB Output is correct
9 Correct 329 ms 40516 KB Output is correct
10 Correct 324 ms 42948 KB Output is correct
11 Correct 331 ms 41412 KB Output is correct
12 Correct 320 ms 42292 KB Output is correct
13 Correct 328 ms 40704 KB Output is correct
14 Correct 321 ms 42580 KB Output is correct
15 Correct 336 ms 42392 KB Output is correct
16 Correct 321 ms 40132 KB Output is correct
17 Correct 325 ms 41920 KB Output is correct
18 Correct 435 ms 40940 KB Output is correct
19 Correct 396 ms 42636 KB Output is correct
20 Correct 332 ms 42844 KB Output is correct
21 Correct 277 ms 40712 KB Output is correct
22 Correct 388 ms 41000 KB Output is correct
23 Correct 278 ms 40900 KB Output is correct
24 Correct 421 ms 41524 KB Output is correct
25 Correct 320 ms 40488 KB Output is correct
26 Correct 434 ms 40596 KB Output is correct
27 Correct 436 ms 43256 KB Output is correct
28 Correct 341 ms 41028 KB Output is correct
29 Correct 373 ms 42296 KB Output is correct
30 Correct 281 ms 40496 KB Output is correct
31 Correct 295 ms 42500 KB Output is correct
32 Correct 287 ms 42308 KB Output is correct
33 Correct 426 ms 40184 KB Output is correct
34 Correct 282 ms 41920 KB Output is correct