Submission #169600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
169600	2019-12-21T10:36:50 Z	SamAnd	Collider (IZhO11_collider)	C++17	100 / 100	250 ms	53372 KB

collider

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(3413);
const int N = 1000006;

int yz;
int yy[N];
void pre()
{
    for (int i = 0; i < N; ++i)
        yy[i] = i;
    for (int i = N - 1; i >= 0; --i)
        swap(yy[i], yy[(rnd() % (i + 1))]);
}

struct ban
{
    ban *l, *r;
    int y;
    char x;
    int q;
    ban(){}
    ban(char x)
    {
        l = r = 0;
        y = yy[yz++];
        this->x = x;
        q = 1;
    }
};
typedef ban* pban;

int getq(pban t)
{
    if (t == 0)
        return 0;
    return t->q;
}

void ubdq(pban t)
{
    if (t == 0)
        return;
    t->q = getq(t->l) + 1 + getq(t->r);
}

void mer(pban l, pban r, pban& t)
{
    if (l == 0)
    {
        t = r;
        return;
    }
    if (r == 0)
    {
        t = l;
        return;
    }
    if (l->y > r->y)
    {
        mer(l->r, r, l->r);
        t = l;
    }
    else
    {
        mer(l, r->l, r->l);
        t = r;
    }
    ubdq(t);
}

void spl(pban t, int x, pban& l, pban& r)
{
    if (t == 0)
    {
        l = 0;
        r = 0;
        return;
    }
    if (x <= getq(t->l))
    {
        spl(t->l, x, l, t->l);
        r = t;
    }
    else
    {
        spl(t->r, x - getq(t->l) - 1, t->r, r);
        l = t;
    }
    ubdq(l);
    ubdq(r);
}

void pb(pban& t, char x)
{
    mer(t, new ban(x), t);
}

void ubd(pban& t, int x, int y)
{
    if (x == y)
        return;
    if (x < y)
    {
        pban t1, t2, t3, t4;
        spl(t, x - 1, t1, t);
        spl(t, 1, t2, t);
        spl(t, y - x, t3, t4);
        mer(t1, t3, t);
        mer(t, t2, t);
        mer(t, t4, t);
    }
    else
    {
        pban t1, t2, t3, t4;
        spl(t, y - 1, t1, t);
        spl(t, x - y, t2, t);
        spl(t, 1, t3, t4);
        mer(t1, t3, t);
        mer(t, t2, t);
        mer(t, t4, t);
    }
}

char qry(pban& t, int x)
{
    pban t1, t2, t3;
    spl(t, x - 1, t1, t);
    spl(t, 1, t2, t3);
    char ans = t2->x;
    mer(t1, t2, t);
    mer(t, t3, t);
    return ans;
}

void pr(pban t)
{
    if (t == 0)
        return;
    pr(t->l);
    printf("%c", t->x);
    pr(t->r);
}

int n, m;
char a[N];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    scanf(" %s", a);
    pre();
    pban t = 0;
    for (int i = 0; i < n; ++i)
        pb(t, a[i]);
    //pr(t);
    //printf("\n");
    while (m--)
    {
        char ty;
        scanf(" %c", &ty);
        if (ty == 'a')
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ubd(t, x, y);
            //pr(t);
            //printf("\n");
        }
        else
        {
            int x;
            scanf("%d", &x);
            printf("%c\n", qry(t, x));
        }
    }
    return 0;
}

Compilation message

collider.cpp: In function 'int main()':
collider.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", a);
     ~~~~~^~~~~~~~~~
collider.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &ty);
         ~~~~~^~~~~~~~~~~~
collider.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	4344 KB	Output is correct
2	Correct	44 ms	4344 KB	Output is correct
3	Correct	60 ms	9208 KB	Output is correct
4	Correct	176 ms	43464 KB	Output is correct
5	Correct	196 ms	43612 KB	Output is correct
6	Correct	223 ms	48412 KB	Output is correct
7	Correct	239 ms	53368 KB	Output is correct
8	Correct	208 ms	53352 KB	Output is correct
9	Correct	250 ms	53372 KB	Output is correct
10	Correct	228 ms	53368 KB	Output is correct