oj.uz

답안 #525784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525784 2022-02-12T21:19:48 Z TheKingAleks 입자 가속기 (IZhO11_collider) C++14
100 / 100
 230 ms 48672 KB 
#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

# 결과 실행 시간 메모리 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