oj.uz

Submission #864612

# Submission time Handle Problem Language Result Execution time Memory
864612 2023-10-23T10:33:27 Z boris_mihov New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 76276 KB 
#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 = 60000 + 10;
const int INF  = 1e9;

// macros as defined above 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
  
typedef __gnu_pbds::tree <int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> oSet;

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];
    oSet tree[4*MAXN];
    void insert(int l, int r, int node, int queryPos, int queryValue)
    {
        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)
    {
        tree[node].erase(tree[node].find(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].order_of_key(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(-i);
        active[i].insert(n + i);
    }

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

    int ptr = -1;
    tree.build(prev);
    std::sort(query + 1, query + 1 + q);
    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 currPrev = prev[idx];
                int next = *it;
                
                tree.update(idx, prev[idx], INF + idx);
                prev[idx] = INF + idx;

                if (next <= n) tree.update(next, prev[next], currPrev);
                prev[next] = currPrev;


                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 = 1e8, 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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 11 ms 24152 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Correct 11 ms 24188 KB Output is correct
5 Correct 15 ms 24412 KB Output is correct
6 Correct 16 ms 24416 KB Output is correct
7 Correct 13 ms 24448 KB Output is correct
8 Correct 15 ms 24428 KB Output is correct
9 Correct 13 ms 24412 KB Output is correct
10 Correct 16 ms 24424 KB Output is correct
11 Correct 14 ms 24156 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 13 ms 24156 KB Output is correct
14 Correct 15 ms 24156 KB Output is correct
15 Correct 15 ms 24408 KB Output is correct
16 Correct 15 ms 24412 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 15 ms 24412 KB Output is correct
19 Correct 15 ms 24396 KB Output is correct
20 Correct 15 ms 24412 KB Output is correct
21 Correct 13 ms 24440 KB Output is correct
22 Correct 14 ms 24408 KB Output is correct
23 Correct 14 ms 24408 KB Output is correct
24 Correct 15 ms 24408 KB Output is correct
25 Correct 15 ms 24416 KB Output is correct
26 Correct 15 ms 24244 KB Output is correct
27 Correct 14 ms 24408 KB Output is correct
28 Correct 15 ms 24156 KB Output is correct
29 Correct 14 ms 24208 KB Output is correct
30 Correct 15 ms 24156 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 11 ms 24152 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Correct 11 ms 24188 KB Output is correct
5 Correct 15 ms 24412 KB Output is correct
6 Correct 16 ms 24416 KB Output is correct
7 Correct 13 ms 24448 KB Output is correct
8 Correct 15 ms 24428 KB Output is correct
9 Correct 13 ms 24412 KB Output is correct
10 Correct 16 ms 24424 KB Output is correct
11 Correct 14 ms 24156 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 13 ms 24156 KB Output is correct
14 Correct 15 ms 24156 KB Output is correct
15 Correct 15 ms 24408 KB Output is correct
16 Correct 15 ms 24412 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 15 ms 24412 KB Output is correct
19 Correct 15 ms 24396 KB Output is correct
20 Correct 15 ms 24412 KB Output is correct
21 Correct 13 ms 24440 KB Output is correct
22 Correct 14 ms 24408 KB Output is correct
23 Correct 14 ms 24408 KB Output is correct
24 Correct 15 ms 24408 KB Output is correct
25 Correct 15 ms 24416 KB Output is correct
26 Correct 15 ms 24244 KB Output is correct
27 Correct 14 ms 24408 KB Output is correct
28 Correct 15 ms 24156 KB Output is correct
29 Correct 14 ms 24208 KB Output is correct
30 Correct 15 ms 24156 KB Output is correct
31 Execution timed out 5044 ms 76276 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 49584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 633 ms 49472 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 11 ms 24152 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Correct 11 ms 24188 KB Output is correct
5 Correct 15 ms 24412 KB Output is correct
6 Correct 16 ms 24416 KB Output is correct
7 Correct 13 ms 24448 KB Output is correct
8 Correct 15 ms 24428 KB Output is correct
9 Correct 13 ms 24412 KB Output is correct
10 Correct 16 ms 24424 KB Output is correct
11 Correct 14 ms 24156 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 13 ms 24156 KB Output is correct
14 Correct 15 ms 24156 KB Output is correct
15 Correct 15 ms 24408 KB Output is correct
16 Correct 15 ms 24412 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 15 ms 24412 KB Output is correct
19 Correct 15 ms 24396 KB Output is correct
20 Correct 15 ms 24412 KB Output is correct
21 Correct 13 ms 24440 KB Output is correct
22 Correct 14 ms 24408 KB Output is correct
23 Correct 14 ms 24408 KB Output is correct
24 Correct 15 ms 24408 KB Output is correct
25 Correct 15 ms 24416 KB Output is correct
26 Correct 15 ms 24244 KB Output is correct
27 Correct 14 ms 24408 KB Output is correct
28 Correct 15 ms 24156 KB Output is correct
29 Correct 14 ms 24208 KB Output is correct
30 Correct 15 ms 24156 KB Output is correct
31 Execution timed out 5044 ms 76276 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 11 ms 24152 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Correct 11 ms 24188 KB Output is correct
5 Correct 15 ms 24412 KB Output is correct
6 Correct 16 ms 24416 KB Output is correct
7 Correct 13 ms 24448 KB Output is correct
8 Correct 15 ms 24428 KB Output is correct
9 Correct 13 ms 24412 KB Output is correct
10 Correct 16 ms 24424 KB Output is correct
11 Correct 14 ms 24156 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Correct 13 ms 24156 KB Output is correct
14 Correct 15 ms 24156 KB Output is correct
15 Correct 15 ms 24408 KB Output is correct
16 Correct 15 ms 24412 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 15 ms 24412 KB Output is correct
19 Correct 15 ms 24396 KB Output is correct
20 Correct 15 ms 24412 KB Output is correct
21 Correct 13 ms 24440 KB Output is correct
22 Correct 14 ms 24408 KB Output is correct
23 Correct 14 ms 24408 KB Output is correct
24 Correct 15 ms 24408 KB Output is correct
25 Correct 15 ms 24416 KB Output is correct
26 Correct 15 ms 24244 KB Output is correct
27 Correct 14 ms 24408 KB Output is correct
28 Correct 15 ms 24156 KB Output is correct
29 Correct 14 ms 24208 KB Output is correct
30 Correct 15 ms 24156 KB Output is correct
31 Execution timed out 5044 ms 76276 KB Time limit exceeded
32 Halted 0 ms 0 KB -