Submission #864557

#	Time	Username	Problem	Language	Result	Execution time	Memory
864557		boris_mihov	New Home (APIO18_new_home)	C++17	0 / 100	5063 ms	405628 KiB

new_home

#include <algorithm>
#include <iostream>
#include <cassert>
#include <chrono>
#include <vector>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

#ifdef DEVAL
    #define cerr if (false) cerr
#endif

typedef long long llong;
const int MAXN = 300000 + 10;
const int INF  = 1e9;

std::mt19937 rngNow(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 rng(69420);

int n, q, k;
struct MergeSortTree
{
    struct Treap
    {
        struct Node
        {
            Node *left, *right;
            int subtreeSize, x, cnt, y;

            Node()
            {
                left = right = nullptr;
            }

            Node(int _x, int _y)
            {
                left = right = nullptr;
                subtreeSize = cnt = 1;
                x = _x; y = _y;
            }
        };

        Node *treap;
        void recover(Node *curr)
        {
            if (curr == nullptr)
            {
                return;
            }

            curr->subtreeSize = curr->cnt;
            if (curr->left != nullptr)
            {
                curr->subtreeSize += curr->left->subtreeSize;
            }

            if (curr->right != nullptr)
            {
                curr->subtreeSize += curr->right->subtreeSize;
            }
        }

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

            if (curr->x <= k)
            {
                left = curr;
                split(curr->right, left->right, right, k);
                recover(left);
            } else
            {
                right = curr;
                split(curr->left, left, right->left, k);
                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)
        {
            Node *l, *ll, *lr, *r;
            split(treap, l, r, value);
            split(l, ll, lr, value - 1);
            if (lr != nullptr)
            {
                lr->cnt++;
                // std::cout << "increment: " << lr->cnt << '\n';
                recover(lr);
            } else
            {
                lr = new Node(value, rng());
            }

            merge(l, ll, lr);
            merge(treap, l, r);
        }

        void erase(int value)
        {
            Node *l, *ll, *lr, *r;
            split(treap, l, r, value);
            split(l, ll, lr, value - 1);
            assert(lr != nullptr);
            if (lr->cnt > 1)
            {
                lr->cnt--;
                // std::cout << "decrement: " << lr->cnt << '\n';
                recover(lr);
            } else
            {
                lr = nullptr;
            }

            merge(l, ll, lr);
            merge(treap, l, r);
        }

        int countLess(int value)
        {
            int res = 0;
            Node *l, *r;
            split(treap, l, r, value - 1);
            if (l != nullptr) res = l->subtreeSize;
            merge(treap, l, r);
            return res;
        }
    };

    Treap tree[4*MAXN];
    void insert(int l, int r, int node, int queryPos, int queryValue)
    {
        // std::cout << "insert: " << l << ' ' << r << '\n' << std::flush;
        tree[node].insert(queryValue);
        if (l == r)
        {
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) insert(l, mid, 2*node, queryPos, queryValue);
        else insert(mid + 1, r, 2*node + 1, queryPos, queryValue);
    }

    void erase(int l, int r, int node, int queryPos, int queryValue)
    {
        // std::cout << "reach: " << l << ' ' << r << '\n' << std::flush;
        tree[node].erase(queryValue);
        if (l == r)
        {
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) erase(l, mid, 2*node, queryPos, queryValue);
        else erase(mid + 1, r, 2*node + 1, queryPos, queryValue);
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node].countLess(queryL);
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void insert(int pos, int value)
    {
        insert(1, n, 1, pos, value);
    }

    void erase(int pos, int value)
    {
        erase(1, n, 1, pos, value);
    }

    int query(int l, int r)
    {
        return query(1, n, 1, l, r);
    }

    void update(int pos, int oldVal, int newVal)
    {
        erase(pos, oldVal);
        insert(pos, newVal);
    }

    void build(int a[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            insert(i, a[i]);
        }
    }
};

struct Store
{
    int pos;
    int l, r;
    int type;

    friend bool operator < (const Store &a, const Store &b)
    {
        return a.pos < b.pos;
    }
};

struct Query
{
    int year;
    int pos;
    int idx;

    friend bool operator < (const Query &a, const Query &b)
    {
        return a.year < b.year;
    }
};

struct StoreEvent
{
    int year;
    int idx;
    int t;

    friend bool operator < (const StoreEvent &a, const StoreEvent &b)
    {
        return a.year < b.year;
    }
};

int a[MAXN];
int prev[MAXN];
int perm[MAXN];
int output[MAXN];
Store store[MAXN];
Query query[MAXN];
std::set <int> active[MAXN];
std::vector <StoreEvent> storeEvent;
MergeSortTree tree;

int searchLast(int value)
{
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (store[mid].pos <= value) l = mid;
        else r = mid;
    }

    return l;
}

int searchFirst(int value)
{
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (store[mid].pos < value) l = mid;
        else r = mid;
    }

    return r;
}

void solve()
{
    std::sort(store + 1, store + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        storeEvent.push_back({store[i].l, i, 0});
        storeEvent.push_back({store[i].r + 1, i, 1});
    }

    for (int i = 1 ; i <= k ; ++i)
    {
        active[i].insert(0);
        active[i].insert(n + 1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        prev[i] = INF;
    }


    int ptr = -1;
    tree.build(prev);
    std::sort(query + 1, query + 1 + n);
    std::sort(storeEvent.begin(), storeEvent.end());

    for (int i = 1 ; i <= q ; ++i)
    {
        while (ptr + 1 < storeEvent.size() && storeEvent[ptr + 1].year <= query[i].year)
        {
            ptr++;
            const auto &[year, idx, t] = storeEvent[ptr];
            if (t == 0)
            {
                auto it = active[store[idx].type].upper_bound(idx);
                int next = *it;
                if (next <= n) tree.update(next, prev[next], idx);
                prev[next] = idx;
                
                it--;
                tree.update(idx, prev[idx], *it);
                prev[idx] = *it;

                active[store[idx].type].insert(idx);
            } else
            {
                auto it = active[store[idx].type].upper_bound(idx);
                int next = *it;
                if (next <= n) tree.update(next, prev[next], prev[idx]);
                prev[next] = prev[idx];

                tree.update(idx, prev[idx], INF);
                prev[idx] = INF;

                active[store[idx].type].erase(active[store[idx].type].find(idx));
            }
        }

        if (tree.query(1, n) < k)
        {
            output[query[i].idx] = -1;
            continue;
        }

        int l = -1, r = 1e9, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            int ll = searchFirst(query[i].pos - mid);
            int rr = searchLast(query[i].pos + mid);

            if (ll > rr || tree.query(ll, rr) < k) l = mid;
            else r = mid;
        }

        output[query[i].idx] = r;
    }
}


void input()
{
    std::cin >> n >> k >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> store[i].pos >> store[i].type >> store[i].l >> store[i].r;
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> query[i].pos >> query[i].year;
        query[i].idx = i;
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << output[i] << '\n';
    }
}

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

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:337:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<StoreEvent>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  337 |         while (ptr + 1 < storeEvent.size() && storeEvent[ptr + 1].year <= query[i].year)
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20