QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729413 | #9543. Good Partitions | 2366503423 | WA | 73ms | 10556kb | C++14 | 2.9kb | 2024-11-09 17:04:08 | 2024-11-09 17:04:09 |
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;cout<<a[1]<<' ';
for(int i=1;i<n;i++)
{
if(w[i-1]>w[i]) a[i+1]=i;
else a[i+1]=0;
cout<<a[i+1]<<' ';
}
cout<<'\n';
build(1,n,1);
cout<<"gcd="<<getgcd2(1,n,1,n,1)<<'\n';
int q;cin>>q;
while(q--)
{
int index,x;cin>>index>>x;
w[index-1]=x;
if(index>1)
{
if(w[index-2]>w[index-1]) update2(index-1,index-1,index-1,1,n,1);
}
if(index<n)
{
if(w[index-1]>w[index]) update2(index,index,index,1,n,1);
}
cout<<'\n'<<"gcd="<<getgcd2(1,n,1,n,1)<<'\n';
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 73ms
memory: 10556kb
input:
1 5 2 4 3 2 6 1 2 5 3 5
output:
0 0 2 3 0 gcd=5 gcd=7
result:
wrong answer 1st lines differ - expected: '1', found: '0 0 2 3 0 '