QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114643#6631. Maximum Bitwise ORwillowWA 97ms10544kbC++143.1kb2023-06-22 18:12:482023-06-22 18:12:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-22 18:12:51]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:10544kb
  • [2023-06-22 18:12:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int T, n, q, a[maxn];
#define lc (o << 1)
#define rc (o << 1 | 1)
#define mid ((l + r) >> 1)
#define lson lc, l, mid
#define rson rc, mid + 1, r
struct Node {
	int v, high;
	Node(int v = 0, int high = -1) : v(v), high(high) {}
	void Init(int x) {
		v = x;
		high = -1;
		if(x) {
			high = 0;
			while((1 << high) <= x)
				++ high;
			-- high;
		}
	}
}tror[maxn << 2];
Node Merge(Node a, Node b) {
	return Node(a.v | b.v, max(a.high, b.high));
}
int Mer(int a, int b) {
	if(a == -1 || b == -1 || (a > 0 && b > 0))
		return -1;
	if(a > 0 && b == 0)
		return a;
	if(b > 0 && a == 0)
		return b;
	return 0;
}
int arr[maxn << 2][32], cnt[maxn << 2][32];
void Build(int o, int l, int r) {
	if(l == r) {
		tror[o].Init(a[l]);
		vector<int> v;
		v.clear();
		v.push_back(-1);
		memset(cnt[o], 0, sizeof cnt[o]);
		for(int j = 0; j < 30; ++ j)
			if(a[l] >> j & 1) {
				v.push_back(j);
				cnt[o][j] = l;
			}
		memset(arr[o], 0x3f, sizeof arr[o]);
		for(int j = 0; j + 1 < (int)v.size(); ++ j) {
			int lp = v[j] + 1, rp = v[j + 1];
// cerr << "Pos: " << l << " " << lp << " " << rp << endl;
			for(int x = lp; x <= rp; ++ x) {
				arr[o][x] = lp;
			}
		}
		return;
	}
	Build(lson), Build(rson);
	tror[o] = Merge(tror[lc], tror[rc]);
	for(int j = 0; j < 32; ++ j) {
		arr[o][j] = min(arr[lc][j], arr[rc][j]);
		cnt[o][j] = Mer(cnt[lc][j], cnt[rc][j]);
	}
}
Node Get(int o, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr)
		return tror[o];
	Node x;
	if(ql <= mid)
		x = Merge(x, Get(lson, ql, qr));
	if(qr > mid)
		x = Merge(x, Get(rson, ql, qr));
	return x;
}
int Ask(int o, int l, int r, int ql, int qr, int rp) {
	if(ql > qr)
		return 1e9;
	if(ql <= l && r <= qr)
		return arr[o][rp];
	int x = 1e9;
	if(ql <= mid)
		x = min(x, Ask(lson, ql, qr, rp));
	if(qr > mid)
		x = min(x, Ask(rson, ql, qr, rp));
	return x;
}
int Que(int o, int l, int r, int ql, int qr, int pos) {
	if(ql <= l && r <= qr)
		return cnt[o][pos];
	int x = 0;
	if(ql <= mid)
		x = Mer(x, Que(lson, ql, qr, pos));
	if(qr > mid)
		x = Mer(x, Que(rson, ql, qr, pos));
	return x;
}
int main() {
	for(scanf("%d", &T); T --; ) {
		scanf("%d%d", &n, &q);
		for(int i = 1; i <= n; ++ i) {
			scanf("%d", &a[i]);
		}
		Build(1, 1, n);
		for(int l, r; q --; ) {
			scanf("%d%d", &l, &r);
			Node now = Get(1, 1, n, l, r);
			// cerr << now.v << " " << now.high << endl;
			assert(now.v < (1 << (now.high + 1)));
			if(now.v == ((1 << (now.high + 1)) - 1)) {
				printf("%d %d\n", now.v, 0);
				continue;
			}
			int lx = 31, rx = -1;
			for(int i = 0; i <= now.high; ++ i) {
				if(!(now.v >> i & 1)) {
					lx = min(lx, i);
					rx = max(rx, i);
				}
			}
			assert(lx <= rx);
			int p = Que(1, 1, n, l, r, now.high);
			int x = Ask(1, 1, n, l, r, rx);
			if(p > 0)
				x = min(Ask(1, 1, n, l, p - 1, rx), Ask(1, 1, n, p + 1, r, rx));
// cerr << Ask(1, 1, n, l, r, rx) << " " << now.v << " " << lx << " " << rx << endl;
			printf("%d %d\n", ((1 << (now.high + 1)) - 1), 1 + (x > lx));
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 10504kb

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: 89ms
memory: 10544kb

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: 97ms
memory: 8948kb

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 1556th numbers differ - expected: '2', found: '1'