oj.uz

Submission #668997

# Submission time Handle Problem Language Result Execution time Memory
668997 2022-12-05T10:41:04 Z boris_mihov Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 3000 ms 36156 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 ; 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
0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3020 ms 36156 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 3058 ms 8676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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