QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117129#6631. Maximum Bitwise ORchenxinyang2006WA 43ms9916kbC++142.6kb2023-06-30 13:20:072023-06-30 13:20:11

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-30 13:20:11]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:9916kb
  • [2023-06-30 13:20:07]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n,q;
int a[100005],pval[100005][35];

pii res[100005];
vector <pii> Qry[100005];
struct info{
	int pos,val;
};
vector <info> P[100005];

int ans[100005];
void upd(int x,int y){
	while(x && ans[x] < y){
		ans[x] = y;
		x--;
	}
}

inline int lowbit(int x) {return x & (-x);}

void recalc(int l,int r){//重新结算 [l,r] 的 ext 值
	int sum = 0,tmp,pos;
	per(i,r,l){
		pos = i;
		per(k,SZ(P[i - 1]) - 1,0){
			tmp = P[i - 1][k].val | sum;
			tmp |= pval[i][ctz(tmp + 1)];
			upd(pos,ctz(tmp + 1));
			pos = P[i - 1][k].pos - 1;
		}
		sum |= a[i];
	}
}

void solve(){
	scanf("%d%d",&n,&q);
	rep(i,1,n){
		scanf("%d",&a[i]);
		Qry[i].clear();
		ans[i] = -1;
		per(k,30,0){
			if(a[i] & (1 << k)) pval[i][k] = 1 << k;
			else pval[i][k] = pval[i][k + 1] | (1 << k);
		}
	}
	rep(i,1,q){
		int l,r;
		scanf("%d%d",&l,&r);
		Qry[r].eb(mkp(l,i));
	}
	rep(r,1,n){
		P[r].clear();
		int pst = -1,pos = r;
		for(info I:P[r - 1]){
			if((I.val | a[r]) != I.val) chkmin(pos,I.pos);
			if((I.val | a[r]) == pst) continue;
			P[r].push_back({I.pos,I.val | a[r]});
			pst = I.val | a[r];
		}
		if(pst != a[r]) P[r].push_back({r,a[r]});
		recalc(max(1,pos - 1),r);
		for(pii I:Qry[r]){
			int tmp = 0;
			for(info II:P[r]) if(II.pos <= I.first) chkmax(tmp,II.val);
//			printf("%d->%d\n",I.second,tmp);

			if(lowbit(tmp + 1) == tmp + 1){
				res[I.second] = mkp(tmp,0);
			}else if(ans[I.first] == __lg(tmp) + 1){
				res[I.second] = mkp((1 << (__lg(tmp) + 1)) - 1,1);
			}else{
				res[I.second] = mkp((1 << (__lg(tmp) + 1)) - 1,2);
			}
		}
	}
	rep(i,1,q) printf("%d %d\n",res[i].first,res[i].second);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

详细

Test #1:

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

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: 39ms
memory: 9740kb

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: 43ms
memory: 9152kb

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
1073741823 2
536870911 2
536870911 2
1073741823 2
1073741823 2...

result:

wrong answer 39th numbers differ - expected: '268435455', found: '1073741823'