Submission #525784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525784	2022-02-12T21:19:48 Z	TheKingAleks	Collider (IZhO11_collider)	C++14	100 / 100	230 ms	48672 KB

collider

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m;
string s;
struct Node
{
    Node *l, *r;
    char val;
    int prior,subtree;
    Node(){}
    Node(char _val)
    {
        l = nullptr;
        r = nullptr;
        val = _val;
        prior = rand();
        subtree = 1;
    }
};
Node* root;
int get_subtree(Node* t)
{
    if(t == nullptr) return 0;
    return t->subtree;
}
void update_subtree(Node* t)
{
    if(t == nullptr) return;
    t->subtree = get_subtree(t->l)+get_subtree(t->r)+1;
    return;
}
pair<Node*, Node*> split(Node* t, int key, int add)
{
    if(t == nullptr) return {nullptr, nullptr};
    int currKey = add+1+get_subtree(t->l);
    if(currKey < key)
    {
        pair<Node*, Node*> tmp = split(t->r, key, currKey);
        t->r = tmp.first;
        update_subtree(t);
        return {t,tmp.second};
    }
    else
    {
        pair<Node*, Node*> tmp = split(t->l, key, add);
        t->l = tmp.second;
        update_subtree(t);
        return {tmp.first, t};
    }
}
Node* merge_treaps(Node* t1, Node* t2)
{
    if(t1 == nullptr) return t2;
    if(t2 == nullptr) return t1;
    if(t1->prior > t2->prior)
    {
        t1->r = merge_treaps(t1->r, t2);
        update_subtree(t1);
        return t1;
    }
    else
    {
        t2->l = merge_treaps(t1, t2->l);
        update_subtree(t2);
        return t2;
    }
}
char get_value(int idx)
{
    pair<Node*, Node*> tmp1 = split(root,idx,0);
    pair<Node*, Node*> tmp2 = split(tmp1.second,2,0);
    char ret = tmp2.first->val;
    tmp1.second = merge_treaps(tmp2.first,tmp2.second);
    root = merge_treaps(tmp1.first, tmp1.second);
    return ret;
}
void erase_value(int idx)
{
    pair<Node*, Node*> tmp1 = split(root,idx,0);
    pair<Node*, Node*> tmp2 = split(tmp1.second,2,0);
    root = merge_treaps(tmp1.first, tmp2.second);
    return;
}
void insert_value(int idx,char new_val)
{
    Node* newTreap = new Node(new_val);
    pair<Node*, Node*> tmp = split(root,idx,0);
    tmp.first = merge_treaps(tmp.first,newTreap);
    root = merge_treaps(tmp.first, tmp.second);
    return;
}
void update_treap(int old_idx, int new_idx)
{
    char transit_value = get_value(old_idx);
    erase_value(old_idx);
    insert_value(new_idx, transit_value);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    cin>>s;
    for(int i=0; i<n; i++)
    {
        insert_value(i+1,s[i]);
    }
    for(int i=0; i<m; i++)
    {
        char type;
        int idx0,idx1;
        cin>>type;
        if(type == 'a')
        {
            cin>>idx0>>idx1;
            if(idx0 == idx1) continue;
            update_treap(idx0,idx1);
        }
        else
        {
            cin>>idx0;
            cout<<get_value(idx0)<<endl;
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	10 ms	716 KB	Output is correct
3	Correct	29 ms	5220 KB	Output is correct
4	Correct	170 ms	38716 KB	Output is correct
5	Correct	185 ms	38964 KB	Output is correct
6	Correct	203 ms	43900 KB	Output is correct
7	Correct	219 ms	48616 KB	Output is correct
8	Correct	203 ms	48364 KB	Output is correct
9	Correct	230 ms	48672 KB	Output is correct
10	Correct	215 ms	48540 KB	Output is correct