Submission #969456

#	Time	Username	Problem	Language	Result	Execution time	Memory
969456		efedmrlr	Measures (CEOI22_measures)	C++17	100 / 100	724 ms	401160 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41