Submission #344398

#	Time	Username	Problem	Language	Result	Execution time	Memory
344398		keko37	Santa Claus (RMI19_santa)	C++14	100 / 100	525 ms	13420 KiB

santa

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 100005;

int tc, n, ofs;
int x[MAXN], h[MAXN], val[MAXN], sol[MAXN];
int t[MAXN * 4], prop[MAXN * 4];
multiset <int> st;

void tour_init () {
    ofs = 1;
    while (ofs < n + 1) ofs *= 2;
    for (int i = 0; i < 2 * ofs; i++) {
        t[i] = prop[i] = 0;
    }
}

void propagate (int x) {
    if (prop[x] == 0) return;
    if (x < ofs) {
        prop[2 * x] += prop[x];
        prop[2 * x + 1] += prop[x];
    }
    t[x] += prop[x];
    prop[x] = 0;
}

void update (int x, int from, int to, int lo, int hi, int d) {
    propagate(x);
    if (from <= lo && hi <= to) {
        prop[x] += d;
        propagate(x);
        return;
    }
    if (to < lo || hi < from) return;
    update(2 * x, from, to, lo, (lo + hi) / 2, d);
    update(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, d);
    t[x] = min(t[2 * x], t[2 * x + 1]);
}

void ispis () {
    for (int i = 1; i <= n; i++) cout << sol[i] << " ";
    cout << '\n';
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> n;
        int rig = -1;
        for (int i = 1; i <= n; i++) cin >> x[i];
        for (int i = 1; i <= n; i++) {
            sol[i] = -1;
            cin >> h[i];
            if (h[i] == 0) rig = i;
        }
        for (int i = 1; i <= n; i++) cin >> val[i];
        if (rig == -1) {
            ispis();
            continue;
        }
        tour_init();
        for (int i = 1; i < rig; i++) {
            update(1, val[i], ofs - 1, 0, ofs - 1, h[i] == 1 ? 1 : -1);
        }
        int lef = 1;
        st.clear();
        for (int i = rig; i <= n; i++) {
            update(1, val[i], ofs - 1, 0, ofs - 1, h[i] == 1 ? 1 : -1);
            while (lef < i && t[1] >= 0) {
                if (h[lef] == 1) {
                    update(1, val[lef], ofs - 1, 0, ofs - 1, -1);
                    auto it = st.lower_bound(val[lef]);
                    if (it != st.end()) {
                        update(1, *it, ofs - 1, 0, ofs - 1, 1);
                        st.erase(it);
                    }
                } else {
                    st.insert(val[lef]);
                }
                lef++;
            }
            if (t[1] < 0) {
                if (lef == 1) sol[i] = -1; else sol[i] = 2 * x[i] - x[lef - 1];
            } else {
                sol[i] = x[i];
            }
        }
        ispis();
    }
    return 0;
}

• Subtask 1: 100 / 100