Submission #861728

#	Time	Username	Problem	Language	Result	Execution time	Memory
861728		arbuzick	Modern Machine (JOI23_ho_t5)	C++17	26 / 100	3103 ms	489048 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        a[i]--;
    }
    if (n == 10 && count(s.begin(), s.end(), 'R') == n) {
        vector<vector<int>> go(n, vector<int>(1 << n));
        for (int mask = 0; mask < (1 << n); ++mask) {
            for (int i = 0; i < n; ++i) {
                int mask_nw = mask;
                if (mask_nw & (1 << i)) {
                    mask_nw ^= (1 << i);
                }
                int pos = i;
                while (0 <= pos && pos < n) {
                    if (mask_nw & (1 << pos)) {
                        mask_nw ^= (1 << pos);
                        pos--;
                    } else {
                        mask_nw ^= (1 << pos);
                        pos++;
                    }
                }
                go[i][mask] = mask_nw;
            }
        }
        vector<int> jump_len(m - 1);
        vector<vector<int>> jump(m, vector<int>(1 << n));
        for (int i = m - 1; i >= 0; --i) {
            if (i + 1 < m && i + 1 + jump_len[i + 1] < m && jump_len[i + 1] == jump_len[i + 1 + jump_len[i + 1]]) {
                jump_len[i] = 1 + jump_len[i + 1] * 2;
                if (jump_len[i] == 3) {
                    for (int mask = 0; mask < (1 << n); ++mask) {
                        jump[i][mask] = go[a[i + 1 + jump_len[i + 1]]][go[a[i + 1]][go[a[i]][mask]]];
                    }
                } else {
                    for (int mask = 0; mask < (1 << n); ++mask) {
                        jump[i][mask] = jump[i + 1 + jump_len[i + 1]][jump[i + 1][go[a[i]][mask]]];
                    }
                }
            } else {
                jump_len[i] = 1;
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            cin >> l >> r;
            l--;
            int mask = 0;
            int pos = l;
            while (pos < r) {
                if (jump_len[pos] > 1 && pos + jump_len[pos] <= r) {
                    mask = jump[pos][mask];
                    pos += jump_len[pos];
                } else {
                    mask = go[a[pos]][mask];
                    // mask = pr[pos][mask];
                    pos++;
                }
            }
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (!(mask & (1 << i))) {
                    cnt++;
                }
            }
            cout << cnt << '\n';
        }
        return;
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        string s_old = s;
        for (int i = l; i < r; ++i) {
            s[a[i]] = 'R';
            int pos = a[i];
            int l_nw = a[i], r_nw = a[i] + 1;
            char ch = 'R';
            while (0 <= pos && pos < n) {
                l_nw = min(l_nw, pos);
                r_nw = max(r_nw, pos + 1);
                if (s[pos] == 'R') {
                    while (r_nw < n && s[r_nw] == 'R') {
                        r_nw++;
                    }
                    ch = 'B';
                    pos = r_nw;
                } else {
                    while (l_nw > 0 && s[l_nw - 1] == 'B') {
                        l_nw--;
                    }
                    ch = 'R';
                    pos = l_nw - 1;
                }
            }
            fill(s.begin() + l_nw, s.begin() + r_nw, ch);
        }
        cout << count(s.begin(), s.end(), 'R') << '\n';
        s = s_old;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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