Submission #344941

#	Time	Username	Problem	Language	Result	Execution time	Memory
344941		nicolaalexandra	Collider (IZhO11_collider)	C++14	100 / 100	342 ms	61676 KiB

collider

#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;
struct treap{
    int val,priority,nr;
    treap *left, *right;
    treap (int val, int priority, int nr, treap *left, treap *right){
        this->val = val;
        this->priority = priority;
        this->nr = nr;
        this->left = left;
        this->right = right;
    }
};
treap *rad, *nil;
int n,q,x,y,poz,i;
char s[DIM];

int get_random(){
    return rand() % (INF-1) + 1;
}

treap* update (treap *rad){
    if (rad == nil)
        rad->val = rad->nr = 0;
    else rad->nr = rad->left->nr + rad->right->nr + 1;

    return rad;
}
/*pair <treap*, treap*> split (treap *rad, int poz){
    rad = update (rad);
    pair <treap*, treap*> ans;

    if (rad == nil)
        return make_pair (nil,nil);

    if (rad->left->nr + 1 > poz){
        ans = split (rad->left,poz);
        rad->left = ans.second;
        ans.second = rad;
    } else {
        ans = split (rad->right,poz - rad->left->nr - 1);
        rad->right = ans.first;
        ans.first = rad;
    }

    rad = update (rad);
    return ans;
}

treap* join (treap *rad1, treap *rad2){
    if (rad1 == nil)
        return rad2;
    if (rad2 == nil)
        return rad1;

    rad1 = update (rad1), rad2 = update (rad2);
    if (rad1->priority <= rad2->priority){

        rad2->left = join (rad1,rad2->left);
        rad2 = update (rad2);
        return rad2;

    }  else {
        rad1->right = join (rad1->right,rad2);
        rad1 = update (rad1);
        return rad1;
    }

    return nil;
}

treap* _insert (treap *rad, int poz, int val, int priority){

    if (rad == nil){
        rad = new treap (val,priority,1,nil,nil);
        rad = update (rad);
        return rad;
    }

    pair<treap*, treap*> aux = split (rad,poz-1);
    rad = new treap (val,priority,1,aux.first,aux.second);
    rad = update(rad);
    return rad;
}

int get_elem (treap *&rad, int poz){

    rad = update (rad);
    if (rad->left->nr + 1 == poz)
        return rad->val;

    else {
        if (rad->left->nr + 1 > poz)
            return get_elem (rad->left,poz);
        else return get_elem (rad->right,poz-rad->left->nr-1);
    }
}


treap* _delete (treap *rad, int x, int y){
    pair <treap*,treap*> aux = split (rad,y);
    pair <treap*,treap*> aux2 = split (aux.first,x-1);

    rad = join (aux2.first, aux.second);
    rad = update (rad);
    return rad;
}*/
pair <treap*, treap*> split (treap *rad, int poz){
    rad = update (rad);
    pair <treap*, treap*> ans;
    if (rad == nil)
        return make_pair (nil,nil);

    if (rad->left->nr >= poz){
        ans = split (rad->left,poz);
        rad->left = ans.second;
        ans.second = rad;
    } else {
        ans = split (rad->right,poz-rad->left->nr-1);
        rad->right = ans.first;
        ans.first = rad;
    }
    rad = update (rad);
    return ans;
}

treap* join (treap *rad1, treap *rad2){
    if (rad1 == nil)
        return rad2;
    if (rad2 == nil)
        return rad1;

    rad1 = update (rad1), rad2 = update (rad2);
    if (rad1->priority > rad2->priority){
        rad1->right = join (rad1->right,rad2);
        rad1 = update (rad1);
        return rad1;
    } else {
        rad2->left = join (rad1,rad2->left);
        rad2 = update (rad2);
        return rad2;
    }
    return nil;
}

treap* _insert (treap *rad, int poz, int val, int priority){

    if (rad == nil){
        rad = new treap (val,priority,1,nil,nil);
        rad = update (rad);
        return rad;
    }

    pair<treap*, treap*> aux = split (rad,poz-1);
    rad = new treap (val,priority,1,aux.first,aux.second);
    rad = update(rad);
    return rad;
}

treap *_delete (treap *rad, int poz){
    pair <treap*, treap*> aux = split (rad,poz);
    pair <treap*, treap*> aux2 = split (aux.first,poz-1);
    rad = join (aux2.first,aux.second);
    rad = update (rad);
    return rad;
}

int access (treap *&rad, int poz){

    rad = update (rad);
    if (rad->left->nr + 1 == poz)
        return rad->val;
    else {
        if (rad->left->nr + 1 > poz)
            return access (rad->left,poz);
        else return access (rad->right,poz-rad->left->nr-1);
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    rad = nil = new treap (0,0,0,NULL,NULL);

    cin>>n>>q>>s+1;
    for (i=1;i<=n;i++){
        int val = s[i] - 'x' + 1;
        rad = _insert (rad,i,val,get_random());
    }

    for (;q--;){
        char tip; cin>>tip;
        if (tip == 'a'){
            cin>>x>>y;
            int val = access (rad,x);
            rad = _delete(rad,x);
            rad = _insert (rad,y,val,get_random());
        } else {
            cin>>poz;
            cout<<char('x' + access(rad,poz) - 1)<<"\n";
        }
    }

    return 0;
}

Compilation message (stderr)

collider.cpp: In function 'int main()':
collider.cpp:189:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  189 |     cin>>n>>q>>s+1;
      |                ~^~

• Subtask 1: 100 / 100