QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122754#6631. Maximum Bitwise ORwnmrmr#RE 0ms0kbC++234.1kb2023-07-11 01:39:342023-07-11 01:39:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 01:39:37]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-11 01:39:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl

#define pb push_back
#define int long long

int n, q;

void solve () {
    cin >> n >> q;
    vector<int> a (n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector last (n + 1, vector<int> (30));
    vector sum_bit (n + 1, vector<int> (30));
    vector freq (n + 1, vector (30, vector<int> (30)));
    vector acum (n + 1, vector (30, vector<int> (30)));
    for (int i = 1; i <= n; i++) {
        last[i] = last[i - 1];
        sum_bit[i] = sum_bit[i - 1];
        acum[i] = acum[i - 1];

        // vamos adicionar o numero
        for (int l = 0; l < 30; l++) {
            // atualizamos o ultimo
            if ((1 << l) & a[i]) last[i][l] = i, sum_bit[i][l]++;

            // atualizamos freq
            freq[i][l][l]++;
            for (int r = l + 1; r < 30; r++) {
                if ((1 << r) & a[i]) break;
                else freq[i][l][r]++;
            }
        }

        for (int l = 0; l < 30; l++) 
            for (int r = l; r < 30; r++)
                acum[i][l][r] += freq[i][l][r];
    }

    auto get_f = [&] (int l, int r) {
        vector f (30, vector<int> (30));
        for (int i = 0; i < 30; i++)
            for (int j = i; j < 30; j++)
                f[i][j] = acum[r][i][j] - acum[l - 1][i][j];
        return f;
    };
    auto get_sum = [&] (int l, int r) {
        vector<int> sum (30);
        for (int i = 0; i < 30; i++) sum[i] = sum_bit[r][i] - sum_bit[l - 1][i];
        return sum;
    };

    while (q--) {
        int l, r; cin >> l >> r;

        auto f = get_f (l, r);
        auto sum = get_sum (l, r);

        int mx = 29;
        while (mx >= 0 && !sum[mx]) mx--;
        // dbg (mx);
        cout << (1 << (mx + 1)) - 1 << " ";
        if (mx < 0) {
            // se o or eh 0
            cout << "0\n";
            continue;
        }
        bool ok = true;
        for (int j = 0; j <= mx; j++) if (!sum[j]) ok = false;
        if (ok) {
            cout << "0\n";
            continue;
        }

        // senao, temos que ver se a resposta eh 1
        // vamos fazer operacao com cada cara 1, e depois vamos ver 

        vector<int> esp;
        for (int j = 0; j < 30; j++) if (sum[j] == 1) {
            // se esse cara eh unico
            esp.pb (last[r][j]);
        }
        sort (all (esp));
        esp.resize (unique (all (esp)) - esp.begin ());

        ok = false;
        for (auto id : esp) {
            // retiramos e vermos se eh possivel
            for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
                f[i][j] -= freq[id][i][j];

            // temos que ver se ainda existe um cara que preenche
            int esq = 30, dir = -1;
            for (int j = 0; j <= mx; j++) if (!f[j][j]) {
                esq = min (esq, j);
                dir = max (dir, j);
            }

            if (freq[id][esq][dir]) {
                ok = true;
            }

            for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
                f[i][j] += freq[id][i][j];
        }

        if (ok) {
            cout << "1\n";
            continue;
        }

        for (auto id : esp) {
            // retiramos e vermos se eh possivel
            for (int i = 0; i < 30; i++) for (int j = i; j < 30; j++)
                f[i][j] -= freq[id][i][j];
        }

        int esq = 30, dir = -1;
        for (int j = 0; j <= mx; j++) if (!f[j][j]) {
            esq = min (esq, j);
            dir = max (dir, j);
        }

        if (f[esq][dir]) {
            ok = true;
        }

        if (ok) {
            cout << "1\n";
            continue;
        }

        cout << "2\n";
    }
}

signed main () {
    ios::sync_with_stdio(0);cin.tie(0);
    int t; cin >> t;
    while (t--)
        solve ();
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

1
3 2
10 10 5
1 2
1 3

output:


result: