Submission #1161510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161510		Der_Vlapos	Modern Machine (JOI23_ho_t5)	C++20	0 / 100	60 ms	9028 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 mySegTree
// {
//     struct Node
//     {
//         int mn = BIG, mx = -1, op = 0;
//     };
//     vector<Node> tree;
//     int sz = 1;
//     int mod;

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

//     void upd(int v, int val)
//     {
//         tree[v].mn = (tree[v].mn + val) % mod;
//         tree[v].mx = (tree[v].mx + val) % mod;
//         assert(tree[v].mn <= tree[v].mx);
//     }

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

//     void merge(int v)
//     {
//         tree[v].mn = min(tree[v * 2 + 1].mn, tree[v * 2 + 2].mn);
//         tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
//     }

//     void set(int pos, int val, int v, int lv, int rv)
//     {
//         push(v, lv, rv);
//         if (rv - lv == 1)
//         {
//             tree[v].mn = tree[v].mx = val;
//             return;
//         }
//         int m = (lv + rv) >> 1;
//         if (pos < m)
//             set(pos, val, v * 2 + 1, lv, m);
//         else
//             set(pos, val, v * 2 + 2, m, rv);
//         merge(v);
//     }

//     void set(int pos, int val)
//     {
//         set(pos, val, 0, 0, sz);
//     }

//     void add(int )
// };

struct DSU
{
    vector<int> p;

    void init(int n)
    {
        p.resize(n);
        for (int i = 0; i < n; ++i)
            p[i] = i;
    }

    int getR(int v)
    {
        return v == p[v] ? v : p[v] = getR(p[v]);
    }

    void merge(int a, int b)
    {
        assert(a == getR(a));
        assert(b == getR(b));
        p[b] = a;
    }
};

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])
                {
                    cntG = i + 1;
                    if (wasOne)
                        good = false;
                }
                else
                {
                    wasOne = true;
                }
            }
        }

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

                {
                    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 q;
            cin >> q;
            vector<int> ans(q);
            vector<vector<pii>> qId(m);
            for (int i = 0; i < q; ++i)
            {
                int l, r;
                cin >> l >> r;
                --l, --r;
                qId[r].pb({l, i});
            }

            vector<int> res(n);
            vector<pii> was(n + 1, {-1, -1});
            vector<pii> uniqueVals;
            DSU dsu;
            dsu.init(m);
            for (int i = 0; i < m; ++i)
            {
                vector<pii> nvals;
                int p = P[i];
                for (auto &[c1, v] : uniqueVals)
                {
                    c1 = (p + (p >= c1) + c1 + 1) % (n + 1);

                    if (was[c1].f == i)
                    {
                        dsu.merge(was[c1].s, v);
                    }
                    else
                    {
                        res[v] = c1;
                        nvals.pb({c1, v});
                        was[c1] = {i, v};
                    }
                }
                uniqueVals = nvals;
                assert(uniqueVals.size() <= n + 10);

                int curVal = (P[i] + (P[i] >= cntG) + cntG + 1) % (n + 1);
                uniqueVals.push_back({curVal, i});
                res[i] = curVal;

                for (auto [l, id] : qId[i])
                {
                    ans[id] = res[dsu.getR(l)];
                }
            }

            for (int i = 0; i < q; ++i)
                cout << ans[i] << "\n";
        }
    }
};

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

Compilation message (stderr)

Main.cpp:355:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  355 | 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