oj.uz

Submission #861728

# Submission time Handle Problem Language Result Execution time Memory
861728 2023-10-16T19:37:57 Z arbuzick Modern Machine (JOI23_ho_t5) C++17
26 / 100
 3000 ms 489048 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 23 ms 512 KB Output is correct
13 Correct 55 ms 344 KB Output is correct
14 Correct 10 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 23 ms 512 KB Output is correct
13 Correct 55 ms 344 KB Output is correct
14 Correct 10 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3062 ms 1628 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 418 ms 488860 KB Output is correct
3 Correct 434 ms 488784 KB Output is correct
4 Correct 415 ms 489044 KB Output is correct
5 Correct 375 ms 488504 KB Output is correct
6 Correct 384 ms 489048 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 418 ms 488860 KB Output is correct
3 Correct 434 ms 488784 KB Output is correct
4 Correct 415 ms 489044 KB Output is correct
5 Correct 375 ms 488504 KB Output is correct
6 Correct 384 ms 489048 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 55 ms 516 KB Output is correct
11 Execution timed out 3103 ms 2140 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 418 ms 488860 KB Output is correct
3 Correct 434 ms 488784 KB Output is correct
4 Correct 415 ms 489044 KB Output is correct
5 Correct 375 ms 488504 KB Output is correct
6 Correct 384 ms 489048 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Execution timed out 3013 ms 1624 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 23 ms 512 KB Output is correct
13 Correct 55 ms 344 KB Output is correct
14 Correct 10 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3062 ms 1628 KB Time limit exceeded
19 Halted 0 ms 0 KB -