oj.uz

Submission #668999

# Submission time Handle Problem Language Result Execution time Memory
668999 2022-12-05T10:42:16 Z boris_mihov Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 26056 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>

typedef long long llong;
const int MAXQ = 1000000 + 10;
const int MAXN = 200000 + 10;
const int INF = 1e9 + 1;

struct Node
{
    int value, y;
    int subtreeMAX;
    int subtreeSize;
    Node *left, *right;

    Node()
    {
        left = right = nullptr;
    }

    Node(int _value, int _y)
    {
        y = _y;
        value = _value;
        subtreeSize = 1;
        subtreeMAX = value;
        left = right = nullptr;
    }
};

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

    curr->subtreeSize = 1;
    curr->subtreeMAX = curr->value;
    if (curr->left != nullptr)
    {
        curr->subtreeSize += curr->left->subtreeSize;
        curr->subtreeMAX = std::max(curr->subtreeMAX, curr->left->subtreeMAX);
    }

    if (curr->right != nullptr)
    {
        curr->subtreeSize += curr->right->subtreeSize;
        curr->subtreeMAX = std::max(curr->subtreeMAX, curr->right->subtreeMAX);
    }
}

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

    int lSize = 1;
    if (curr->left != nullptr) 
    {
        lSize += curr->left->subtreeSize;
    }
    
    if (k >= lSize)
    {
        left = curr;
        split(curr->right, left->right, right, k - lSize);
        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);
}

inline void pushBack(Node *&curr, int value)
{
    Node *newNode = new Node(value, rand());
    merge(curr, curr, newNode);
}

int findFirstBigger(Node *curr, int value)
{
    assert(curr != nullptr);
    assert(curr->subtreeMAX > value);
    int lSize = 1;
    if (curr->left != nullptr) 
    {
        lSize += curr->left->subtreeSize;
    }

    if ((curr->left == nullptr || curr->left->subtreeMAX < value) && curr->value > value) 
    {
        return lSize;
    }

    if (curr->left != nullptr && curr->left->subtreeMAX > value) return findFirstBigger(curr->left, value);
    return findFirstBigger(curr->right, value) + lSize;
}

inline int getElement(Node *curr, int which)
{
    Node *left, *lleft, *element, *right;
    split(curr, left, right, which);
    split(left, lleft, element, which - 1);
    int value = element->value;
    merge(left, lleft, element);
    merge(curr, left, right);
    return value;
}

Node *left, *right;
struct Query
{
    int idx;
    int pos;
    int time;

    inline friend bool operator < (const Query &a, const Query &b)
    {
        return a.time < b.time || (a.time == b.time && a.idx < b.idx);
    }
};

int n, q;
int a[MAXN];
int b[MAXN];
Query queries[MAXQ];
int ans[MAXQ];

void solve()
{
    left = right = nullptr;
    for (int i = 1 ; i <= n/2 ; ++i)
    {
        pushBack(left, a[i]);
        pushBack(right, a[n/2 + i]);
    }

    int qPtr = 1;
    std::sort(queries + 1, queries + 1 + q);
    for (int shuffle = 0 ; shuffle <= n && qPtr <= q ; ++shuffle)
    {
        while (queries[qPtr].time == shuffle && qPtr <= q) 
        {
            if (queries[qPtr].pos <= n/2) ans[queries[qPtr].idx] = getElement(left, queries[qPtr].pos);
            else ans[queries[qPtr].idx] = getElement(right, queries[qPtr].pos - n/2);
            qPtr++;
        }

        int reachedTo = 0;
        while (right != nullptr && left->subtreeMAX > getElement(right, 1))
        {
            Node *rightFirst, *rrright;
            split(right, rightFirst, rrright, 1); right = rrright;
            Node *lleft, *rright, *rl, *rr;
            split(left, lleft, rright, reachedTo);
            int pos = findFirstBigger(rright, rightFirst->value);
            reachedTo += pos;
            split(rright, rl, rr, pos - 1);
            merge(rl, rl, rightFirst);
            merge(rright, rl, rr);
            merge(left, lleft, rright);
        }

        assert(left->subtreeSize >= n/2);
        Node *lright;
        split(left, left, lright, n/2);
        merge(right, lright, right);

        // std::cout << "after shuffle #" << shuffle + 1 << '\n';
        // for (int i = 1 ; i <= n/2 ; ++i) std::cout << getElement(left, i) << ' ';
        // for (int i = 1 ; i <= n/2 ; ++i) std::cout << getElement(right, i) << ' '; std::cout << '\n';
    }

    while (qPtr <= q) 
    {
        if (queries[qPtr].pos <= n/2) ans[queries[qPtr].idx] = getElement(left, queries[qPtr].pos);
        else ans[queries[qPtr].idx] = getElement(right, queries[qPtr].pos - n/2);
        qPtr++;
    }

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

void read()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

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

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

int main()
{
    srand(69420);
    fastIO();
    read();
    solve();
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 19864 KB Output is correct
2 Correct 747 ms 25264 KB Output is correct
3 Correct 801 ms 24352 KB Output is correct
4 Correct 711 ms 25100 KB Output is correct
5 Correct 755 ms 25728 KB Output is correct
6 Correct 684 ms 24736 KB Output is correct
7 Correct 727 ms 25076 KB Output is correct
8 Correct 720 ms 24312 KB Output is correct
9 Correct 658 ms 24424 KB Output is correct
10 Correct 664 ms 24732 KB Output is correct
11 Correct 685 ms 24140 KB Output is correct
12 Correct 627 ms 23672 KB Output is correct
13 Correct 668 ms 23896 KB Output is correct
14 Correct 723 ms 26028 KB Output is correct
15 Correct 732 ms 26056 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 702 ms 24604 KB Output is correct
18 Correct 661 ms 24460 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 22168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 6836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 19864 KB Output is correct
2 Correct 747 ms 25264 KB Output is correct
3 Correct 801 ms 24352 KB Output is correct
4 Correct 711 ms 25100 KB Output is correct
5 Correct 755 ms 25728 KB Output is correct
6 Correct 684 ms 24736 KB Output is correct
7 Correct 727 ms 25076 KB Output is correct
8 Correct 720 ms 24312 KB Output is correct
9 Correct 658 ms 24424 KB Output is correct
10 Correct 664 ms 24732 KB Output is correct
11 Correct 685 ms 24140 KB Output is correct
12 Correct 627 ms 23672 KB Output is correct
13 Correct 668 ms 23896 KB Output is correct
14 Correct 723 ms 26028 KB Output is correct
15 Correct 732 ms 26056 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 702 ms 24604 KB Output is correct
18 Correct 661 ms 24460 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Execution timed out 3073 ms 22168 KB Time limit exceeded
22 Halted 0 ms 0 KB -