oj.uz

Submission #969456

# Submission time Handle Problem Language Result Execution time Memory
969456 2024-04-25T07:52:20 Z efedmrlr Measures (CEOI22_measures) C++17
100 / 100
 724 ms 401160 KB 
#include <bits/stdc++.h>

#define int long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.begin(), x.end()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e17;

struct Node {
    int mn, mx, sum, tag;
    int lc, rc;
    Node() : mn(INF), mx(-INF), sum(0), tag(0), lc(-1), rc(-1) {}
};

int D;

struct SegT {
    const int MX = 1e9 + 5;
    vector<Node> st;
    int pt = 0;
    int create_node() {
        st.pb(Node());
        return pt++;
    }   

    void reset() {
        pt = 0;
        st.clear();
        create_node();
    }

    void extend(int v) {
        if(st[v].lc == -1) st[v].lc = create_node();
        if(st[v].rc == -1) st[v].rc = create_node();
    }
    void push(int v) {
        st[st[v].lc].mn += st[v].tag;
        st[st[v].lc].mx += st[v].tag;
        st[st[v].lc].tag += st[v].tag;

        st[st[v].rc].mn += st[v].tag;
        st[st[v].rc].mx += st[v].tag; 
        st[st[v].rc].tag += st[v].tag;

        st[v].tag = 0;
    }
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            st[v].mn += val;
            st[v].mx += val;
            st[v].tag += val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        int tm = (tl + tr) >> 1;
        extend(v); push(v);
        update(tl, tm, st[v].lc, l, r, val);
        update(tm + 1, tr, st[v].rc, l, r, val);
        st[v].mn = min(st[st[v].lc].mn, st[st[v].rc].mn);
        st[v].mx = max(st[st[v].lc].mx, st[st[v].rc].mx);
    }
    int get_ind(int tl, int tr, int v, int r) {
        if(tr <= r) {
            return st[v].sum;
        }
        if(tl > r) return 0;
        int tm = (tl + tr) >> 1;
        extend(v); push(v);
        return get_ind(tl, tm, st[v].lc, r) + get_ind(tm + 1, tr, st[v].rc, r);
    }
    void ins(int tl, int tr, int v, int ind, int val) {
        if(tl == tr) {
            st[v].sum++;
            st[v].mn = min(st[v].mn, val);
            st[v].mx = max(st[v].mx, val);
            return;
        }
        int tm = (tl + tr) >> 1;
        extend(v); push(v);
        if(ind <= tm) {
            ins(tl, tm, st[v].lc, ind, val);
        }
        else {
            ins(tm + 1, tr, st[v].rc, ind, val);
        }
        st[v].mn = min(st[st[v].lc].mn, st[st[v].rc].mn);
        st[v].mx = max(st[st[v].lc].mx, st[st[v].rc].mx);
        st[v].sum = st[st[v].lc].sum + st[st[v].rc].sum;
    }
    int query_mx(int tl, int tr, int v, int r) {
        if(tr <= r) {
            return st[v].mx;
        }
        if(tl > r) return -INF;
        int tm = (tl + tr) >> 1;
        extend(v); push(v);
        return max(query_mx(tl, tm, st[v].lc, r), query_mx(tm + 1, tr, st[v].rc, r));
    }
    int query_mn(int tl, int tr, int v, int l) {
        if(tl >= l) {
            return st[v].mn;
        }
        if(l > tr) {
            return INF;
        }
        int tm = (tl + tr) >> 1;
        extend(v); push(v);
        return min(query_mn(tl, tm, st[v].lc, l), query_mn(tm + 1, tr, st[v].rc, l));
    }
    int insert(int ind) {
        int i = get_ind(0, MX, 0, ind);
        int val = ind - i * D;
        // cout << "ind:" << ind << " i:" << i << "val:" << val << "\n";
        ins(0, MX, 0, ind, val);
        update(0, MX, 0, ind + 1, MX, -D);
        // cout << "mx:" << query_mx(0, MX, 0, ind) << "\n";
        // cout << "mn:" << query_mn(0, MX, 0, ind) << "\n";
        int ret = query_mx(0, MX, 0, ind) - query_mn(0, MX, 0, ind);
        return max(0ll, ret);
    }
};
SegT st;
void solve() {
    int n, m;
    cin >> n >> m >> D;
    int ans = 0;
    st.reset();
    if(n > 0) {
        REP(i, n) {
            int a;
            cin >> a;
            ans = max(ans, st.insert(a));
        }
    }
    REP(i, m) {
        int b;
        cin >> b;
        ans= max(ans, st.insert(b));
        if(ans & 1) {
            cout << ans / 2;
            cout << ".5 ";
        }
        else {
            cout << ans / 2 << " ";
        }
    }
    cout << "\n";
}

signed main() {
    fastio();
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7880 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 8 ms 7884 KB Output is correct
5 Correct 6 ms 3536 KB Output is correct
6 Correct 9 ms 7628 KB Output is correct
7 Correct 5 ms 2004 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7880 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 8 ms 7884 KB Output is correct
5 Correct 6 ms 3536 KB Output is correct
6 Correct 9 ms 7628 KB Output is correct
7 Correct 5 ms 2004 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 724 ms 395072 KB Output is correct
10 Correct 580 ms 398212 KB Output is correct
11 Correct 296 ms 2240 KB Output is correct
12 Correct 501 ms 397596 KB Output is correct
13 Correct 379 ms 100000 KB Output is correct
14 Correct 486 ms 398572 KB Output is correct
15 Correct 366 ms 26028 KB Output is correct
16 Correct 485 ms 397192 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 396712 KB Output is correct
2 Correct 499 ms 399496 KB Output is correct
3 Correct 329 ms 5204 KB Output is correct
4 Correct 495 ms 397772 KB Output is correct
5 Correct 503 ms 399780 KB Output is correct
6 Correct 498 ms 398672 KB Output is correct
7 Correct 515 ms 399408 KB Output is correct
8 Correct 494 ms 398664 KB Output is correct
9 Correct 528 ms 397984 KB Output is correct
10 Correct 506 ms 399240 KB Output is correct
11 Correct 502 ms 398980 KB Output is correct
12 Correct 502 ms 399844 KB Output is correct
13 Correct 498 ms 398972 KB Output is correct
14 Correct 505 ms 398664 KB Output is correct
15 Correct 513 ms 400004 KB Output is correct
16 Correct 396 ms 201356 KB Output is correct
17 Correct 507 ms 398988 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 396712 KB Output is correct
2 Correct 499 ms 399496 KB Output is correct
3 Correct 329 ms 5204 KB Output is correct
4 Correct 495 ms 397772 KB Output is correct
5 Correct 503 ms 399780 KB Output is correct
6 Correct 498 ms 398672 KB Output is correct
7 Correct 515 ms 399408 KB Output is correct
8 Correct 494 ms 398664 KB Output is correct
9 Correct 528 ms 397984 KB Output is correct
10 Correct 506 ms 399240 KB Output is correct
11 Correct 502 ms 398980 KB Output is correct
12 Correct 502 ms 399844 KB Output is correct
13 Correct 498 ms 398972 KB Output is correct
14 Correct 505 ms 398664 KB Output is correct
15 Correct 513 ms 400004 KB Output is correct
16 Correct 396 ms 201356 KB Output is correct
17 Correct 507 ms 398988 KB Output is correct
18 Correct 588 ms 398472 KB Output is correct
19 Correct 602 ms 399268 KB Output is correct
20 Correct 328 ms 5228 KB Output is correct
21 Correct 513 ms 398436 KB Output is correct
22 Correct 565 ms 398404 KB Output is correct
23 Correct 491 ms 397440 KB Output is correct
24 Correct 600 ms 399704 KB Output is correct
25 Correct 493 ms 397448 KB Output is correct
26 Correct 585 ms 398228 KB Output is correct
27 Correct 601 ms 401160 KB Output is correct
28 Correct 615 ms 398724 KB Output is correct
29 Correct 589 ms 398624 KB Output is correct
30 Correct 556 ms 397424 KB Output is correct
31 Correct 515 ms 400108 KB Output is correct
32 Correct 505 ms 400772 KB Output is correct
33 Correct 480 ms 200852 KB Output is correct
34 Correct 507 ms 398392 KB Output is correct