Submission #17867

#	Time	Username	Problem	Language	Result	Execution time	Memory
17867		Elibay	Collider (IZhO11_collider)	C++14	100 / 100	593 ms	49680 KiB

collider

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1e6 + 17, INF = 1e9;

int n, m;
char c[MaxN];

struct node
{
    int cnt, y, x;
    node *l, *r;
    node (int X = INF)
    {
        cnt = 1;
        x = X;
        y = rand ();
        l = r = NULL;
    }
} *t;
typedef node* pnode;

int GetSz (pnode t)
{
    if (!t)
        return 0;
    return t -> cnt;
}
int GetKey (pnode t)
{
    if (!t)
        return 0;
    return GetSz (t -> l) + 1;
}
void upd (pnode &t)
{
    if (!t)
        return;
    t -> cnt = GetSz(t -> l) + GetSz (t -> r) + 1;
}
pnode Merge (pnode a, pnode b)
{
    if (!a)
        return b;
    if (!b)
        return a;
    if (a -> y > b -> y)
    {
        a -> r = Merge (a -> r, b);
        upd (a);
        return a;
    }
    else
    {
        b -> l = Merge (a, b -> l);
        upd (b);
        return b;
    }
}
void Split (pnode t, int x, pnode &a, pnode &b)
{
    if (!t)
        return void (a = b = NULL);
    int cnt = GetKey (t);
    if (cnt <= x)
    {
        Split (t -> r, x - cnt, t -> r, b);
        a = t;
    }
    else
    {
        Split (t -> l, x, a, t -> l);
        b = t;
    }
    upd (a);
    upd (b);
}
void print (pnode t)
{
    if (!t)
        return;
    print (t -> l);
    cerr << c[t -> x];
    print (t -> r);
}
void add (int pos)
{
    pnode L, R, M;
    L = R = M = NULL;
    Split (t, pos + 1, L, R);
    Split (L, pos, L, M);
    M = Merge (new node (pos), M);
    L = Merge (L, M);
    t = Merge (L, R);    
}
void Upd (int pos1, int pos2)
{
    pnode L, R, A, B, M;
    L = R = A = B = M = NULL;
    if (pos1 > pos2)
    {
        Split (t, pos1, L, R);
        Split (L, pos1 - 1, L, A);
        Split (L, pos2 - 1, L, M);
        M = Merge (A, M);
        L = Merge (L, M);
        t = Merge (L, R);
    }
    else
    {
        Split (t, pos1, L, R);
        Split (L, pos1 - 1, L, A);
        Split (R, pos2 - pos1, M, R);
        M = Merge (M, A);
        L = Merge (L, M);
        t = Merge (L, R);
    }
/*    cerr << pos1 << ' ' << pos2 << endl;
    print (t);
    cerr << endl;*/
}
int GetZ (int pos)
{
    pnode L, R, M;
    L = R = M = NULL;
    Split (t, pos, L, R);
    Split (L, pos - 1, L, M);
    int w = M -> x;
    L = Merge (L, M);
    t = Merge (L, R);
    return w;    
}
int main ()
{
    ios_base :: sync_with_stdio (0);
    #ifdef Elibay
        freopen (".in", "r", stdin);
//        freopen (".err", "w", stderr);
    #endif
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> c[i], add (i);
    for (int i = 1; i <= m; ++ i)
    {
        char cc;
        int x, y;
        cin >> cc;
        if (cc == 'a')
        {
            cin >> x >> y;
            Upd (x, y);
        }
        else
        {
            cin >> x;
            cout << c[GetZ(x)] << "\n";
        }
    }
    return 0;
}

• Subtask 1: 100 / 100