QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153862 | #6405. Barkley | qzez | WA | 4ms | 20864kb | C++14 | 1.9kb | 2023-08-31 09:26:44 | 2023-08-31 09:26:45 |
Judging History
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'