QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153862#6405. BarkleyqzezWA 4ms20864kbC++141.9kb2023-08-31 09:26:442023-08-31 09:26:45

Judging History

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

  • [2023-08-31 09:26:45]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:20864kb
  • [2023-08-31 09:26:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e5+10,K=__lg(N)+2;
int n,m;
ll a[N];
struct zj{
	ll val;
	int id;
};
using vs=vector<zj>;
vs merge(const vs &A,const vs &B){
	if(A.empty())return B;
	vs C=A;
	for(zj x:B){
		if(x.val%C.back().val){
			ll v=__gcd(x.val,C.back().val);
			C.push_back({v,x.id});
		}
	}
	return C;
}
vs t[N<<2];
void build(int l=1,int r=n,int rt=1){
	if(l==r){
		t[rt]={{a[l],l}};return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	t[rt]=merge(t[rt<<1],t[rt<<1|1]);
}
void query(int L,int R,vs &ans,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R){
		ans=merge(ans,t[rt]);return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)query(L,R,ans,l,mid,rt<<1);
	if(mid<R)query(L,R,ans,mid+1,r,rt<<1|1);
}
ll f[K][N];
void init(){
	for(int i=1;i<=n;i++)f[0][i]=a[i];
	for(int i=1;(1<<i)<=n;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			f[i][j]=__gcd(f[i-1][j],f[i-1][j+(1<<i-1)]);
		}
	}
}
ll calc(int l,int r){
	if(l>r)return 0;
	int k=__lg(r-l+1);
	return __gcd(f[k][l],f[k][r-(1<<k)+1]);
}
ll calc(int l,int r,int k){
	if(l>r)return 0;
	if(!k)return calc(l,r);
	vs ans;
	query(l,r,ans);
	ll res=0;
	for(zj x:ans){
		res=max(res,__gcd(calc(l,x.id-1),calc(x.id+1,r,k-1)));
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(),init();
	for(int l,r,k;m--;){
		scanf("%d%d%d",&l,&r,&k);
		printf("%lld\n",calc(l,r,k));
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 16836kb

input:

4 4
3 2 6 4
1 3 1
2 4 1
1 4 2
1 4 3

output:

3
2
3
6

result:

ok 4 number(s): "3 2 3 6"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 20864kb

input:

100 10000
7 25 33 17 13 33 24 29 11 1 3 19 2 20 33 23 14 24 15 12 3 1 5 13 6 35 15 21 10 34 31 19 7 33 17 26 26 1 19 21 31 5 29 20 18 32 19 18 19 31 11 26 6 19 2 26 23 1 4 2 31 21 29 30 1 14 20 23 14 32 4 34 13 29 5 26 24 29 28 5 26 26 21 19 2 33 2 31 30 3 23 24 26 32 36 21 21 11 5 9
56 57 1
90 97 1...

output:

26
1
1
1
1
1
1
1
31
1
1
1
1
1
26
1
1
1
1
1
1
29
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
21
1
1
1
1
1
19
1
1
1
21
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
3
1
2
1
26
1
1
1
1
1
1
1
7
1
1
1
33
1
1
1
1
1
1
2
1
26
1
1
1
2
1
1
1
1
1
1
26
1
1
1
1
31
1
1
2
1
4
29
1
2
1
1...

result:

wrong answer 7823rd numbers differ - expected: '2', found: '1'