QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877512#9738. Make It DivisiblexielirenML 0ms3840kbC++141.6kb2025-01-31 22:54:582025-01-31 22:55:05

Judging History

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

  • [2025-01-31 22:55:05]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3840kb
  • [2025-01-31 22:54:58]
  • 提交

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...

output:


result: