oj.uz

Submission #937696

# Submission time Handle Problem Language Result Execution time Memory
937696 2024-03-04T11:21:12 Z zwezdinv Modern Machine (JOI23_ho_t5) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, m;
        std::cin >> n >> m;
        std::string c;
        std::cin >> c;
        int st = 0;
        for (int i = 0; i < n; ++i) {
                st |= (c[i] == 'R') << i;
        }
        std::vector<std::vector<int>> ss(1 << n, std::vector<int>(n));
        for (int mask = 0; mask < 1 << n; ++mask) {
                for (int i = 0; i < n; ++i) {
                        int m4sk = mask;
                        int ptr = i;
                        m4sk |= 1 << i;
                        while (0 <= ptr && ptr < n) {
                                m4sk ^= 1 << ptr;
                                if (~m4sk >> ptr & 1) {
                                        ptr++;
                                } else {
                                        ptr--;
                                }
                        }
                        ss[mask][i] = m4sk;
                }
        }
        std::vector<int> a(m);
        for (auto& i : a) std::cin >> i, --i;
        std::vector<int> qq(1 << n, -1);
        std::vector<int> pos(m, -1);
        std::vector<int> leader(m, -1);
        std::vector<std::vector<std::pair<int, int>>> que(m);
        int q;
        std::cin >> q;
        std::vector<int> ans(q);
        for (int i = 0; i < q; ++i) {
                int l, r;
                std::cin >> l >> r;
                --l, --r;
                que[r].emplace_back(l, i);
        }
        for (int i = 0; i < m; ++i) {
                if (qq[st] == -1) {
                        qq[st] = i;
                        pos[i] = st;
                        leader[i] = i;
                } else {
                        leader[i] = qq[st];
                }
                std::vector<int> nw(1 << n, -1);
                for (int j = 0; j < 1 << n; ++j) {
                        if (qq[j] == -1) continue;
                        int k = ss[j][a[i]];
                        if (nw[k] != -1) {
                                leader[qq[j]] = nw[k];
                        } else {
                                nw[k] = qq[j];
                        }
                }
                qq = nw;
                for (auto [l, id] : que[i]) {
                        ans[id] = __builtin_popcount(pos[leader[l]]);
                }
        }
        for (auto i : ans) std::cout << i << '\n';
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -