QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#176922#6631. Maximum Bitwise ORUNos_mariconesWA 114ms14152kbC++202.4kb2023-09-12 10:26:282023-09-12 10:26:29

Judging History

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

  • [2023-09-12 10:26:29]
  • 评测
  • 测评结果:WA
  • 用时:114ms
  • 内存:14152kb
  • [2023-09-12 10:26:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std ;

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll SQ = 800;
const ll N = 1e5+5;
const ll mod = 998244353;
const ll oo = 1e18;


vector <int> hv[30][30];
int psum[30][N];

int main(){
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int t; cin >> t;
  while (t--) {
     int n, q; cin >> n >> q;
     vector <int> a(n);
     for (auto &e : a) cin >> e;
     for(int j =0;j<30;++j){
        for(int k=0;k<30;++k) hv[j][k].clear();
     }
     for (int i = 0; i < n; ++i) {
        for (int j = 29; j >= 0; --j) {
           if (i) psum[j][i] = psum[j][i-1];
           else psum[j][i]=0;
        }
        for (int j = 29; j >= 0; --j) {
            if (a[i] & (1<<j)) {
               psum[j][i]++;
               int sj = j;
               while (j > 0 && (a[i] & (1<<(j-1))) > 0) j--;
               for (int k = sj; k >= j; --k) {
                  for(int h = k; h >= j; --h) hv[k][h].pb(i);
               }
            }
        }
     }
     for (int i = 0; i < q; i++) {
        int l,r; cin >> l >> r;
        r--;l--;
        int yet = 0;
        int mx = -1, mn;
        int unq = (1<<30)-1;
        int pp = -1;
        for (int j = 29; j >= 0; --j) {
           int v = psum[j][r] - (l ? psum[j][l-1] : 0);
           if (v >= 1) {
              if (v == 1) unq ^= (1<<j);
              yet=1;
              pp = max(pp, j);
           }
           else {
              if (yet) {
                 if (mx == -1) mx = j;
                 mn = j;
              }
           }
        }
        int desired = (1 << (pp+1))-1;
        if (mx == -1) cout << desired << " " << 0 << '\n';
        else {
          int fs = lower_bound(hv[mx][mn].begin(), hv[mx][mn].end(), l) - hv[mx][mn].begin();
          int can = 2;
          while (fs < hv[mx][mn].size() && hv[mx][mn][fs] <= r) {
            int idx = hv[mx][mn][fs];
            if ((unq & a[idx]) == a[idx]) {
              can = 1;
              break;
            }
            fs++;
          }
          cout << desired << ' ' << can << '\n';
        }
     }
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 14136kb

input:

1
3 2
10 10 5
1 2
1 3

output:

15 2
15 0

result:

ok 4 number(s): "15 2 15 0"

Test #2:

score: 0
Accepted
time: 114ms
memory: 11936kb

input:

100000
1 1
924704060
1 1
1 1
149840457
1 1
1 1
515267304
1 1
1 1
635378394
1 1
1 1
416239424
1 1
1 1
960156404
1 1
1 1
431278082
1 1
1 1
629009153
1 1
1 1
140374311
1 1
1 1
245014761
1 1
1 1
445512399
1 1
1 1
43894730
1 1
1 1
129731646
1 1
1 1
711065534
1 1
1 1
322643984
1 1
1 1
482420443
1 1
1 1
20...

output:

1073741823 2
268435455 2
536870911 2
1073741823 2
536870911 2
1073741823 2
536870911 2
1073741823 2
268435455 2
268435455 2
536870911 2
67108863 2
134217727 2
1073741823 2
536870911 2
536870911 2
268435455 2
536870911 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
16777215 2
10737418...

result:

ok 200000 numbers

Test #3:

score: -100
Wrong Answer
time: 92ms
memory: 14152kb

input:

50000
2 2
924896435 917026400
1 2
1 2
2 2
322948517 499114106
1 2
2 2
2 2
152908571 242548777
1 1
1 2
2 2
636974385 763173214
1 2
1 1
2 2
164965132 862298613
1 1
1 2
2 2
315078033 401694789
1 2
1 2
2 2
961358343 969300127
2 2
1 2
2 2
500628228 28065329
1 2
1 2
2 2
862229381 863649944
1 2
2 2
2 2
541...

output:

1073741823 2
1073741823 2
536870911 2
536870911 2
268435455 2
268435455 2
1073741823 2
1073741823 2
268435455 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
268435455 2
536870911 2
536870911 2
1073741823 2
1073741823 2
...

result:

wrong answer 36426th numbers differ - expected: '0', found: '2'