# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516343 | Be_dos | Collider (IZhO11_collider) | C++17 | 157 ms | 49508 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |