Submission #649850

#	Time	Username	Problem	Language	Result	Execution time	Memory
649850		boris_mihov	Santa Claus (RMI19_santa)	C++17	100 / 100	376 ms	19052 KiB

santa

#include <algorithm>
#include <iostream>
#include <tgmath.h>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>

typedef long long llong; 
const int MAXN = 100000 + 10;
const int MOD  = 1e9 + 7;
const int INF  = 1e9;

struct House
{
    int x, h, v;
    inline friend bool operator < (const House &a, const House &b)
    {
        return a.x < b.x || (a.x == b.x && a.h < b.h) || (a.x == b.x && a.h == b.h && a.v < b.v);
    }
} houses[MAXN];

int n, t;
int x[MAXN];
int h[MAXN];
int v[MAXN];

struct Node
{
    Node *left, *right;
    int ones, zeros;
    int value, type;
    int cnt;
    int y;

    Node()
    {
        left = right = nullptr;
    }

    Node(int _value, int _type, int _y)
    {
        left = right = nullptr; 
        value = _value;
        type = _type;
        cnt = 1;
        zeros = (type == 0) * cnt;
        ones = (type == 1) * cnt;
        y = _y;
    }
};

Node *treap;
void recover(Node *curr)
{
    if (curr == nullptr) return;
    curr->ones = 0;
    curr->zeros = 0;
    if (curr->left != nullptr)
    {
        curr->ones = curr->left->ones;
        curr->zeros = curr->left->zeros;
    }

    curr->ones = curr->ones + std::max(0, (curr->type == 1 ? curr->cnt : 0) - curr->zeros);
    curr->zeros = (curr->type == 0 ? curr->cnt : 0)  + std::max(0, curr->zeros - (curr->type == 1 ? curr->cnt : 0));

    if (curr->right != nullptr)
    {
        curr->ones = curr->ones + std::max(0, curr->right->ones - curr->zeros);
        curr->zeros = curr->right->zeros + std::max(0, curr->zeros - curr->right->ones);
    }
}

inline bool cmp(std::pair <int,bool> x, std::pair <int,bool> y)
{
    return x.first > y.first || (x.first == y.first && x.second < y.second);
}

void split(Node *curr, Node *&left, Node *&right, std::pair <int,bool> value)
{
    if (curr == nullptr)
    {
        left = right = nullptr;
        return;
    }

    if (cmp({curr->value, curr->type}, value))
    {
        left = curr;
        split(curr->right, left->right, right, value);
        recover(left);
    } else
    {
        right = curr;
        split(curr->left, left, right->left, value);
        recover(right);
    }
}

void split2(Node *curr, Node *&left, Node *&right, std::pair <int,bool> value)
{
    if (curr == nullptr)
    {
        left = right = nullptr;
        return;
    }

    if (value.first == curr->value && value.second == curr->type)
    {
        left = curr;
        split2(curr->right, left->right, right, value);
        recover(left);
    } else
    {
        right = curr;
        split2(curr->left, left, right->left, value);
        recover(right);
    }
}

void merge(Node *&curr, Node *left, Node *right)
{
    if (left == nullptr)
    {
        curr = right;
        return;
    }

    if (right == nullptr)
    {
        curr = left;
        return;
    }

    if (left->y > right->y)
    {
        curr = left;
        merge(curr->right, left->right, right);
    } else
    {
        curr = right;
        merge(curr->left, left, right->left);
    }

    recover(curr);
}

void insert(int value, bool type)
{
    Node *l, *r, *rr, *rl, *r1;
    split(treap, l, r, {value, type});
    split2(r, rl, rr, {value, type});
    if (rl == nullptr) rl = new Node(value, type, rand());
    else
    {
        rl->cnt++;
        recover(rl);
    }
    merge(r1, rl, rr);
    merge(treap, l, r1);
}

void erase(int value, bool type)
{
    Node *l, *r, *rr, *rl, *r1;
    split(treap, l, r, {value, type});
    split2(r, rl, rr, {value, type});
    if (rl->cnt == 1) rl = nullptr;
    else 
    {
        rl->cnt--;
        recover(rl);
    }
    merge(r1, rl, rr);
    merge(treap, l, r1);
}

std::multiset <int> toGive;
int maxElvePos;
int minElveIdx;
void solve()
{
    toGive.clear();
    treap = nullptr;
    int ptr = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        insert(v[i], h[i]);
        if (x[i] < maxElvePos || (treap != nullptr && treap->zeros != 0))
        {
            std::cout << -1 << ' ';
            continue;
        }

        while (ptr + 1 < i)
        {
            if (h[ptr + 1] == 0)
            {
                toGive.insert(v[ptr + 1]);
                ptr++;
                continue;
            } else
            {
                int erased = -1;
                auto it = toGive.lower_bound(v[ptr + 1]);
                erase(v[ptr + 1], h[ptr + 1]);
                if (it != toGive.end())
                {
                    erased = *it;
                    erase(*it, 0);
                    toGive.erase(it);
                }

                if (treap != nullptr && treap->zeros >= 1)
                {
                    insert(v[ptr + 1], h[ptr + 1]);
                    if (erased != -1)
                    {
                        insert(erased, 0);
                        toGive.insert(erased);
                    }

                    break;
                } else
                {
                    ptr++;
                }
            }
        }

        std::cout << 2*x[i] - x[ptr + 1] << ' ';
    }

    std::cout << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].x;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].h;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].v;
    std::sort(houses + 1, houses + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = houses[i].x;
        h[i] = houses[i].h;
        v[i] = houses[i].v;
        if (h[i] == 0) 
        {
            maxElvePos = x[i];
            minElveIdx = i;
        }
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    srand(time(nullptr));
    fastIO();
    std::cin >> t;
    while (t--)
    {
        read();
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100