QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #863584 | #9738. Make It Divisible | 22016020736 | TL | 0ms | 8056kb | C++14 | 3.6kb | 2025-01-19 19:31:58 | 2025-01-19 19:31:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int arr[20000009];
int brr[20000009];
map<int,vector<int>>pos;
int st[2000009][30];
bool f;
void init(int n)
{
for(int i=1;i<30;i++)
{
for(int j=1;j+(1<<i)-1<=n;j++)
{
st[j][i]=min(st[j][i-1],st[j+(1ll<<(i-1))][i-1]);
}
}
}
int get(int l,int r)
{
int k=__lg(r-l+1);
return min(st[l][k],st[r-(1ll<<k)+1][k]);
}
void check(int l,int r,int val,int n)
{
//printf("l,r:%lld %lld %lld\n",l,r,val);
//if(!f) return ;
if(l>=r)
{
return ;
}
int mn=get(l,r);///1 4 3 4
//printf("mn:%lld %lld %lld %lld\n",l,r,mn,val);
//printf("l,r:%lld %lld %lld %lld\n",l,r,val,pos[mn].front());
//_sleep(1000);
// for(int i=l;i<=r;i++)
//{
// if( (brr[i]+val)%(mn+val)!=0) f=false;
//}
int pre=l-1;
int idx=lower_bound(pos[mn].begin(),pos[mn].end(),l)-pos[mn].begin();
// while(!pos[mn].empty()&&pos[mn].front()<l) pos[mn].pop_front();
for(int i=idx;i<pos[mn].size();i++)
{
int x=pos[mn][idx];
//if(l==3&&r==4) printf("x:%lld %lld\n",x,val);
if(x-1>r) break;
// printf("11111\n");
if(pre+1<=x-1)
{
int mx=get(pre+1,x-1);
if((mx+val)%(mn+val)!=0) f=false;
check(pre+1,x-1,val,n);
}
pre=x;
}
// while(!pos[mn].empty()&&pos[mn].front()<=r) pos[mn].pop_front();
if(pre!=r)
{
int mx=get(pre+1,r);
if((mx+val)%(mn+val)!=0) f=false;
check(pre+1,r,val,n);
}
}
signed main() {
int tt=0;
//if(3%(1==0) ) printf("aaaaa\n");
scanf("%lld",&tt);
int tmpt=tt;
int t=0;
while(tt--)
{
t++;
int top=0;
set<int>stt;
int n,k;
scanf("%lld%lld",&n,&k);
pos.clear();
int mx=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
brr[i]=x;
mx=max(mx,x);
stt.insert(x);
pos[x].push_back(i);
st[i][0]=x;
}
init(n);
for(int i=1;i<=n;i++)
{
// for(int j=i;j<=n;j++) printf("l,r:%d %d %d\n",i,j,get(i,j));
}
if(tmpt==500&&t==474)
{
// for(int i=1;i<=n;i++) printf("%lld ",brr[i]);
// printf("\n");
}
//return 0;
if(stt.size()==1)
{
int ans=k,sum=k*(k+1)/2;
printf("%lld %lld\n",ans,sum);
continue;
}
for(auto x:stt)
{
arr[++top]=x;
}
int nx=get(1,n);;
if(nx>=mx)
{
printf("0 0\n");
continue;
}
else
{
int shu=mx-nx;
set<int>xulie;
for(int i=1;i*i<=shu;i++)
{
if(shu%i==0)
{
if(i-nx>=1&&i-nx<=k)
xulie.insert(i-nx);
if(shu/i-nx>=1&&shu/i-nx<=k)
xulie.insert(shu/i-nx);
}
}
int ans=0,sum=0;
for(auto x:xulie)
{
f=true;
check(1,n,x,n);
//pos.clear();
//for(int i=1;i<=n;i++) pos[brr[i]].push_back(i);
//printf("777:%lld\n",pos[7].front());
// if(f) printf("x:%lld\n",x);
if(f) ans++,sum+=x;
}
printf("%lld %lld\n",ans,sum);
}
}
return 0;
}
/*
1000
4 1000000000
11 1 22 11
10000
6 1000
8 2 4 3 1 9
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8012kb
input:
3 5 10 7 79 1 7 1 2 1000000000 1 2 1 100 1000000000
output:
3 8 0 0 100 5050
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 8056kb
input:
4 201 1000000000 1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...
output:
0 0 0 0 0 0 0 0
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 8016kb
input:
500 4 1000000000 8 14 24 18 4 1000000000 17 10 18 14 4 1000000000 6 17 19 19 4 1000000000 15 14 15 25 4 1000000000 16 16 5 25 4 1000000000 4 30 20 5 4 1000000000 11 4 23 9 4 1000000000 14 25 13 2 4 1000000000 18 18 1 15 4 1000000000 22 22 22 28 4 1000000000 15 17 17 10 4 1000000000 22 14 13 25 4 100...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500 lines
Test #4:
score: -100
Time Limit Exceeded
input:
1 50000 1000000000 230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 ...