QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#877512 | #9738. Make It Divisible | xieliren | ML | 0ms | 3840kb | C++14 | 1.6kb | 2025-01-31 22:54:58 | 2025-01-31 22:55:05 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){
int s = 0, f = 1;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
return s * f;
}
void write(int x){
if(x < 0){putchar('-'); x = -x;}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int MAXN = 5e4 + 5;
int t, n, k, top, cnt, a[MAXN], ls[MAXN], rs[MAXN], stk[MAXN], minn;
LL res;
bool check(int rt, int x){
if(!rt)return 1;
if(ls[rt] && ((a[ls[rt]] + x) % (a[rt] + x) != 0))return 0;
if(rs[rt] && ((a[rs[rt]] + x) % (a[rt] + x) != 0))return 0;
return check(ls[rt], x) && check(rs[rt], x);
}
void check2(int x){
if(x > k || x < 1)return ;
if(check(stk[1], x))cnt ++, res += x;
}
int main(){
t = read();
while(t --){
n = read(), k = read();
cnt = res = top = 0;
for(int i = 1;i <= n;i ++)a[i] = read(), ls[i] = rs[i] = stk[i] = 0;
top = 0;
for(int i = 1;i <= n;i ++){
while(top && a[stk[top]] > a[i])top --;
ls[i] = rs[stk[top]];
rs[stk[top]] = i;
stk[++ top] = i;
}
bool flag = 1;
for(int i = 1;i <= n;i ++)flag &= (a[i] == a[1]);
if(flag){
printf("%d %lld\n", k, 1ll * k * (k + 1) / 2);
continue;
}
int tmp = 0;
for(int i = 1;i <= n;i ++){
if(ls[i] && !tmp)
tmp = a[ls[i]] - a[i], minn = a[i];
if(rs[i] && !tmp)
tmp = a[rs[i]] - a[i], minn = a[i];
}
for(int i = 1;i * i <= tmp;i ++){
if(tmp % i == 0){
if(i * i != tmp)check2(i - minn);
check2(tmp / i - minn);
}
}
printf("%d %lld\n", cnt, res);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
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: -100
Memory Limit Exceeded
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...