QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729224 | #9543. Good Partitions | 2366503423 | WA | 73ms | 10416kb | C++14 | 2.3kb | 2024-11-09 16:44:10 | 2024-11-09 16:44:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int d[4*300005];
int a[300005];
int b[4*300005];
bool v[4*300005];
int yin[200005];
void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = s + ((t - s) >> 1);
// 移位运算符的优先级小于加减法,所以加上括号
// 如果写成 (s + t) >> 1 可能会超出 int 范围
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}
void update2(int l, int r, int c, int s, int t, int p) {
if (l <= s && t <= r) {
d[p] = (t - s + 1) * c, b[p] = c, v[p] = 1;
return;
}
int m = s + ((t - s) >> 1);
// 额外数组储存是否修改值
if (v[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
b[p * 2] = b[p * 2 + 1] = b[p];
v[p * 2] = v[p * 2 + 1] = 1;
v[p] = 0;
}
if (l <= m) update2(l, r, c, s, m, p * 2);
if (r > m) update2(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
int getgcd2(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) return d[p];
int m = s + ((t - s) >> 1);
if (v[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
b[p * 2] = b[p * 2 + 1] = b[p];
v[p * 2] = v[p * 2 + 1] = 1;
v[p] = 0;
}
int gcd = 0;
if (l <= m) gcd = getgcd2(l, r, s, m, p * 2);
if (r > m) gcd = __gcd(gcd , getgcd2(l, r, m + 1, t, p * 2 + 1) );
return gcd;
}
int main()
{
for(int j=1;j<=200005;j++)
{
int sum=0;
int N=j;
for (int i = 2; i <= N /i; i++)
{
if (N % i == 0)
{
while (N % i == 0) N /= i;// 如果 i 能够整除 N,说明 i 为 N 的一个质因子。
sum++;
}
}
if (N != 1) sum++; // 说明再经过操作之后 N 留下了一个素数
yin[j]=sum;
}
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector <int> w(n,0);
for(int i=0;i<n;i++) cin>>w[i];
a[1]=0;
for(int i=1;i<n;i++)
{
if(w[i-1]>w[i]) a[i+1]=i+1;
else a[i+1]=0;
}
build(1,n,1);
cout<<getgcd2(1,n,1,n,1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 73ms
memory: 10416kb
input:
1 5 2 4 3 2 6 1 2 5 3 5
output:
7
result:
wrong answer 1st lines differ - expected: '1', found: '7'