Submission #443557

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443557	2021-07-10T19:24:22 Z	valerikk	Santa Claus (RMI19_santa)	C++17	100 / 100	401 ms	8364 KB

santa

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const int N = 5e5;

int n;
int x[N], type[N], val[N];
int res[N];
int sum[4 * N], min_sum[4 * N];
int taken[N];

void add(int i, int l, int r, int pos, int delta) {
    if (r - l == 1) {
        sum[i] += delta;
        min_sum[i] += delta;
    } else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            add(2 * i, l, mid, pos, delta);
        } else {
            add(2 * i + 1, mid, r, pos, delta);
        }
        sum[i] = sum[2 * i] + sum[2 * i + 1];
        min_sum[i] = min(min_sum[2 * i], sum[2 * i] + min_sum[2 * i + 1]);
    }
}

void go(int l, int t) {
    if (type[l] == 1) {
        add(1, 0, n, val[l], -1 * t);
        if (taken[l] != -1) {
            add(1, 0, n, taken[l], 1 * t);
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> type[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }

    vector<int> vals;
    for (int i = 0; i < n; i++) {
        vals.push_back(val[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < n; i++) {
        val[i] = lower_bound(vals.begin(), vals.end(), val[i]) - vals.begin();
    }

    int need = 0;
    for (int i = 0; i < n; i++) {
        if (type[i] == 0) {
            need++;
            type[i] = -1;
        }
    }

    multiset<int> s;
    for (int i = 0; i < n; i++) {
        if (type[i] == -1) {
            s.insert(val[i]);
        } else {
            auto it = s.lower_bound(val[i]);
            if (it != s.end()) {
                taken[i] = *it;
                s.erase(it);
            } else {
                taken[i] = -1;
            }
        }
    }

    for (int i = 0; i < 4 * n; i++) {
        sum[i] = 0;
        min_sum[i] = 0;
    }

    int r = n;
    for (int i = 0; i < n; i++) {
        if (type[i] == -1) {
            need--;
        }
        add(1, 0, n, val[i], type[i]);
        if (need == 0 && min_sum[1] >= 0) {
            r = i;
            break;
        }
    }
    for (int i = 0; i < r; i++) {
        res[i] = -1;
    }
    int l = 0;
    for (; r < n; r++) {
        while (l < r) {
            go(l, 1);
            if (min_sum[1] < 0) {
                go(l, -1);
                break;
            }

            l++;
        }

        res[r] = 2 * x[r] - x[l];
        if (r + 1 != n) {
            add(1, 0, n, val[r + 1], 1);
        }
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	8 ms	496 KB	Output is correct
4	Correct	22 ms	664 KB	Output is correct
5	Correct	44 ms	976 KB	Output is correct
6	Correct	74 ms	1672 KB	Output is correct
7	Correct	139 ms	2816 KB	Output is correct
8	Correct	245 ms	4092 KB	Output is correct
9	Correct	271 ms	7076 KB	Output is correct
10	Correct	401 ms	8364 KB	Output is correct