Submission #516343

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516343	2022-01-21T07:07:34 Z	Be_dos	Collider (IZhO11_collider)	C++17	100 / 100	157 ms	49508 KB

collider

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

std::mt19937 rng;
struct Node {
    Node* left = nullptr, *right = nullptr;
    int32_t priority;
    int32_t subtree_size = 1;
    char val;

    Node(char val_) {
        priority = rng() % 10'000'000;
        val = val_;
    }
};

int32_t get_subtree_size(Node* node) {
    if(node == nullptr)
        return 0;
    return node->subtree_size;
}

void recalc(Node* node) {
    node->subtree_size = 1 + get_subtree_size(node->left) + get_subtree_size(node->right);
}

Node* get_by_ind(Node* node, int32_t ind) {
    if(ind == get_subtree_size(node->left))
        return node;
    if(ind < get_subtree_size(node->left))
        return get_by_ind(node->left, ind);
    return get_by_ind(node->right, ind - get_subtree_size(node->left) - 1);
}

std::pair<Node*, Node*> split(Node* node, int32_t left) {
    if(node == nullptr)
        return {nullptr, nullptr};
    if(left <= get_subtree_size(node->left)) {
        std::pair<Node*, Node*> res = split(node->left, left);
        node->left = res.second;
        recalc(node);
        return {res.first, node};
    } else {
        std::pair<Node*, Node*> res = split(node->right, left - get_subtree_size(node->left) - 1);
        node->right = res.first;
        recalc(node);
        return {node, res.second};
    }
}

Node* merge(Node* node1, Node* node2) {
    if(node1 == nullptr)
        return node2;
    if(node2 == nullptr)
        return node1;
    if(node1->priority < node2->priority) {
        node1->right = merge(node1->right, node2);
        recalc(node1);
        return node1;
    } else {
        node2->left = merge(node1, node2->left);
        recalc(node2);
        return node2;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, num_q;
    std::cin >> n >> num_q;

    std::string str;
    std::cin >> str;

    Node* root = nullptr;
    for(int32_t i = 0; i < n; i++)
        root = merge(root, new Node(str[i]));

    for(int32_t q = 0; q < num_q; q++) {
        char type;
        std::cin >> type;

        if(type == 'a') {
            int32_t ind1, ind2;
            std::cin >> ind1 >> ind2;
            ind1--;
            ind2--;

            if(ind1 == ind2)
                continue;

            if(ind2 > ind1) {
                std::pair<Node*, Node*> parts = split(root, ind1);
                std::pair<Node*, Node*> parts2 = split(parts.second, 1);
                std::pair<Node*, Node*> parts3 = split(parts2.second, ind2 - ind1);
                root = merge(parts.first, merge(parts3.first, merge(parts2.first, parts3.second)));
            } else {
                std::pair<Node*, Node*> parts = split(root, ind1);
                std::pair<Node*, Node*> parts2 = split(parts.second, 1);
                std::pair<Node*, Node*> parts3 = split(parts.first, ind2);
                root = merge(parts3.first, merge(parts2.first, merge(parts3.second, parts2.second)));
            }
        } else {
            int32_t ind;
            std::cin >> ind;
            ind--;

            std::cout << get_by_ind(root, ind)->val << "\n";
        }
    }
    return 0;
}
         
         

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	6 ms	464 KB	Output is correct
3	Correct	17 ms	5188 KB	Output is correct
4	Correct	118 ms	39472 KB	Output is correct
5	Correct	114 ms	39580 KB	Output is correct
6	Correct	135 ms	44472 KB	Output is correct
7	Correct	142 ms	49296 KB	Output is correct
8	Correct	123 ms	49200 KB	Output is correct
9	Correct	151 ms	49508 KB	Output is correct
10	Correct	157 ms	49348 KB	Output is correct