oj.uz

Submission #669002

# Submission time Handle Problem Language Result Execution time Memory
669002 2022-12-05T10:46:44 Z boris_mihov Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 22108 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(9539659);
    fastIO();
    read();
    solve();
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 19860 KB Output is correct
2 Correct 728 ms 19924 KB Output is correct
3 Correct 717 ms 19116 KB Output is correct
4 Correct 677 ms 19004 KB Output is correct
5 Correct 730 ms 19792 KB Output is correct
6 Correct 668 ms 19112 KB Output is correct
7 Correct 696 ms 19820 KB Output is correct
8 Correct 640 ms 19132 KB Output is correct
9 Correct 675 ms 18964 KB Output is correct
10 Correct 688 ms 19288 KB Output is correct
11 Correct 670 ms 19152 KB Output is correct
12 Correct 627 ms 19004 KB Output is correct
13 Correct 660 ms 19300 KB Output is correct
14 Correct 662 ms 19560 KB Output is correct
15 Correct 686 ms 19760 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 645 ms 19244 KB Output is correct
18 Correct 639 ms 19012 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 22108 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 3060 ms 7184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 19860 KB Output is correct
2 Correct 728 ms 19924 KB Output is correct
3 Correct 717 ms 19116 KB Output is correct
4 Correct 677 ms 19004 KB Output is correct
5 Correct 730 ms 19792 KB Output is correct
6 Correct 668 ms 19112 KB Output is correct
7 Correct 696 ms 19820 KB Output is correct
8 Correct 640 ms 19132 KB Output is correct
9 Correct 675 ms 18964 KB Output is correct
10 Correct 688 ms 19288 KB Output is correct
11 Correct 670 ms 19152 KB Output is correct
12 Correct 627 ms 19004 KB Output is correct
13 Correct 660 ms 19300 KB Output is correct
14 Correct 662 ms 19560 KB Output is correct
15 Correct 686 ms 19760 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 645 ms 19244 KB Output is correct
18 Correct 639 ms 19012 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Execution timed out 3051 ms 22108 KB Time limit exceeded
22 Halted 0 ms 0 KB -