Submission #1161457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161457		Der_Vlapos	Modern Machine (JOI23_ho_t5)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

const int BIG = 1e9 + 10;
#define int ll

struct segTreeSum
{
    vector<pii> tree;
    int sz;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz, {0, -1});
    }

    void upd(int v, int lv, int rv, int val)
    {
        tree[v].f = (rv - lv) * val;
        tree[v].s = val;
    }

    void push(int v, int lv, int rv)
    {
        if (rv - lv == 1 or tree[v].s == -1)
            return;
        int m = (lv + rv) >> 1;
        upd(v * 2 + 1, lv, m, tree[v].s);
        upd(v * 2 + 2, m, rv, tree[v].s);
        tree[v].s = -1;
    }

    void set(int l, int r, int val, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
        {
            upd(v, lv, rv, val);
            return;
        }
        if (rv <= l or r <= lv)
            return;
        int m = (lv + rv) >> 1;
        set(l, r, val, v * 2 + 1, lv, m);
        set(l, r, val, v * 2 + 2, m, rv);
        tree[v].f = tree[v * 2 + 1].f + tree[v * 2 + 2].f;
    }

    void set(int l, int r, int val)
    {
        set(l, r, val, 0, 0, sz);
    }

    int get(int l, int r, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
            return tree[v].f;
        if (r <= lv or rv <= l)
            return 0;
        int m = (lv + rv) >> 1;
        return get(l, r, v * 2 + 1, lv, m) + get(l, r, v * 2 + 2, m, rv);
    }

    int get(int l, int r)
    {
        return get(l, r, 0, 0, sz);
    }

    int getKthFromStart(int k, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
        {
            assert(k == 0);
            return lv;
        }
        int m = (lv + rv) >> 1;
        if (tree[v * 2 + 1].f <= k)
            return getKthFromStart(k - tree[v * 2 + 1].f, v * 2 + 2, m, rv);
        return getKthFromStart(k, v * 2 + 1, lv, m);
    }

    int getKthFromStart(int k)
    {
        return getKthFromStart(k, 0, 0, sz);
    }

    int getKthFromEnd(int k, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
        {
            assert(k == 0);
            return lv;
        }
        int m = (lv + rv) >> 1;
        if (tree[v * 2 + 2].f <= k)
        {
            return getKthFromEnd(k - tree[v * 2 + 2].f, v * 2 + 1, lv, m);
        }
        return getKthFromEnd(k, v * 2 + 2, m, rv);
    }

    int getKthFromEnd(int k)
    {
        return getKthFromEnd(k, 0, 0, sz);
    }
};

struct test
{
    void solve()
    {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        vector<segTreeSum> tree(2);

        tree[0].init(n);
        tree[1].init(n);

        for (int i = 0; i < n; ++i)
        {
            char x;
            cin >> x;
            a[i] = x == 'R';
            tree[a[i]].set(i, i + 1, 1);
        }
        vector<int> P(m);
        for (int i = 0; i < m; ++i)
        {
            cin >> P[i];
            P[i]--;
        }

        bool good = true;
        int cntG = 0;
        {
            bool wasOne = false;
            for (int i = 0; i < n; ++i)
            {
                if (a[i])
                    wasOne = true;
                else
                {
                    if (wasOne)
                        good = false;
                    cntG = i + 1;
                }
            }
        }

        int q;
        cin >> q;
        auto bf = a;
        for (int i = 0; i < q; ++i)
        {
            int l, r;
            cin >> l >> r;
            --l, --r;

            if (!good)
            {
                for (int i = 0; i < n; ++i)
                {
                    tree[a[i]].set(i, i + 1, 1);
                    tree[1 - a[i]].set(i, i + 1, 0);
                }

                for (int i = l; i <= r; ++i)
                {
                    int p = P[i];
                    tree[1].set(p, p + 1, 1);
                    tree[0].set(p, p + 1, 0);
                    int c1 = tree[0].get(p, n);
                    int c2 = tree[1].get(0, p + 1);
                    if (c1 >= c2)
                    {
                        int leftMostPos = tree[0].getKthFromStart(tree[0].get(0, p + 1) + c2 - 1);
                        tree[0].set(0, leftMostPos + 1, 0);
                        tree[1].set(0, leftMostPos + 1, 1);
                    }
                    else
                    {
                        int rightMostPos = tree[1].getKthFromEnd(tree[1].get(p + 1, n) + c1);
                        tree[0].set(rightMostPos, n, 1);
                        tree[1].set(rightMostPos, n, 0);
                    }
                }

                cout << tree[1].get(0, n) << "\n";
            }
            else
            {
                int c1 = cntG;
                for (int i = l; i <= r; ++i)
                {
                    int p = P[i];
                    c1 = (p + (p >= c1) + c1 + 1) % (n + 1);
                }
                cout << c1 << "\n";
            }
        }
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

Main.cpp:219:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  219 | main()
      | ^~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 12
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21