Submission #478874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478874	2021-10-08T16:52:56 Z	Alexandruabcde	Santa Claus (RMI19_santa)	C++14	100 / 100	339 ms	12100 KB

santa

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;

int N;

int X[NMAX];
int H[NMAX];
int V[NMAX];
int vf = 0;

int ans[NMAX];

struct NOD {
    int a;
    int lazy;
};

NOD Arbore[4*NMAX];

void Propag (int node, int a, int b) {
    if (a == b) return;
    if (Arbore[node].lazy == 0) return;

    int aux = Arbore[node].lazy;
    Arbore[2*node].lazy += aux;
    Arbore[2*node+1].lazy += aux;
    Arbore[2*node].a += aux;
    Arbore[2*node+1].a += aux;

    Arbore[node].lazy = 0;
}

void Update (int node, int a, int b, int ua, int ub, int val) {
    if (ua <= a && b <= ub) {
        Arbore[node].a += val;
        Arbore[node].lazy += val;

        return;
    }

    Propag(node, a, b);

    int mij = (a + b) / 2;

    if (ua <= mij) Update(2*node, a, mij, ua, ub, val);
    if (mij < ub) Update(2*node+1, mij+1, b, ua, ub, val);

    Arbore[node].a = min(Arbore[2*node].a, Arbore[2*node+1].a);
}

int Best () {
    return Arbore[1].a;
}

void Read () {
    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> X[i];
    for (int i = 1; i <= N; ++ i )
        cin >> H[i];
    for (int i = 1; i <= N; ++ i )
        cin >> V[i];
}

void Normalize () {
    map <int, int> mp;

    for (int i = 1; i <= N; ++ i )
        mp[V[i]] = 1;

    vf = 0;
    for (auto &it : mp)
        it.second = ++ vf;

    for (int i = 1; i <= N; ++ i )
        V[i] = mp[V[i]];
}

void Solve () {
    Normalize();

    int Last_Present = N;
    while (Last_Present >= 1 && H[Last_Present]) -- Last_Present;

    assert(1 <= Last_Present && Last_Present <= N);

    for (int i = 1; i <= N; ++ i )
        ans[i] = -1;

    for (int i = 1; i <= Last_Present; ++ i )
        if (H[i]) Update(1, 1, vf, V[i], vf, 1);
        else Update(1, 1, vf, V[i], vf, -1);

    map <int, int> S;
    for (int i = 1; i <= N; ++ i ) {
        if (i > Last_Present) {
            ++ Last_Present;

            if (H[Last_Present]) Update(1, 1, vf, V[Last_Present], vf, 1);
            else Update(1, 1, vf, V[Last_Present], vf, -1);
        }

        while (Last_Present < N && Best() < 0) {
            ++ Last_Present;

            if (H[Last_Present]) Update(1, 1, vf, V[Last_Present], vf, 1);
            else Update(1, 1, vf, V[Last_Present], vf, -1);
        }

        if (Best() >= 0) ans[Last_Present] = i;

        if (H[i] == 0) {
            S[V[i]] ++;;
        }
        else {
            auto it = S.lower_bound(V[i]);

            if (it != S.end()) {
                Update(1, 1, vf, it->first, vf, 1);
            }
            -- it->second;
            if (it->second == 0) S.erase(it);

            Update(1, 1, vf, V[i], vf, -1);
        }
    }

    for (int i = 2; i <= N; ++ i )
        ans[i] = max(ans[i-1], ans[i]);

    for (int i = 1; i <= N; ++ i ) {
        if (ans[i] == -1) {
            cout << -1 << " ";
        }
        else cout << 2LL * X[i] - X[ans[i]] << " ";
    }
    cout << '\n';
}

void Reset () {
    for (int i = 0; i <= N; ++ i )
        ans[i] = -1;
    for (int i = 1; i <= 4 * N; ++ i )
        Arbore[i].a = Arbore[i].lazy = 0;
}

void Do_Testcase () {
    Read();
    Solve();
    Reset();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;

    for (; T; -- T )
        Do_Testcase();

    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	7 ms	460 KB	Output is correct
4	Correct	17 ms	576 KB	Output is correct
5	Correct	35 ms	924 KB	Output is correct
6	Correct	62 ms	1328 KB	Output is correct
7	Correct	112 ms	2432 KB	Output is correct
8	Correct	175 ms	3468 KB	Output is correct
9	Correct	212 ms	9300 KB	Output is correct
10	Correct	339 ms	12100 KB	Output is correct