QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114987#6631. Maximum Bitwise ORappleseWA 150ms10760kbC++143.4kb2023-06-24 13:15:312023-06-24 13:15:31

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-24 13:15:31]
  • 评测
  • 测评结果:WA
  • 用时:150ms
  • 内存:10760kb
  • [2023-06-24 13:15:31]
  • 提交

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;
}
vector<int> v;
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);
			v.clear();
			v.push_back(l - 1);
			v.push_back(r + 1);
			for(int i = 0; i <= now.high; ++ i) {
				int p = Que(1, 1, n, l, r, i);
				if(p > 0) {
					v.push_back(p);
				}
			}
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
			int x = 1e9;
			for(int i = 0; i + 1 < (int)v.size(); ++ i)
				x = min(x, Ask(1, 1, n, v[i] + 1, v[i + 1] - 1, rx));
// cerr << p << " " << x << " " << lx << " " << rx << endl;
// 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: 2ms
memory: 10144kb

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: 116ms
memory: 10072kb

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: 0
Accepted
time: 118ms
memory: 10100kb

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:

ok 200000 numbers

Test #4:

score: -100
Wrong Answer
time: 150ms
memory: 10760kb

input:

33333
3 3
925088809 339284112 289540728
3 3
1 3
1 1
3 3
422399522 892365243 216341776
3 3
3 3
1 2
3 3
668932010 837523227 840095874
1 3
1 3
3 3
3 3
731584574 357877180 359063739
1 1
1 1
3 3
3 3
463358343 833924976 847087403
2 3
3 3
1 2
3 3
377154649 772000701 656357011
2 3
1 2
2 3
3 3
977492169 5540...

output:

536870911 2
1073741823 2
1073741823 2
268435455 2
268435455 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
536870911 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
1073741823 2
67108863 2
1073741823 2
1073741...

result:

wrong answer 9322nd numbers differ - expected: '1', found: '2'