QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726957 | #9543. Good Partitions | Cabbage | WA | 42ms | 11460kb | C++14 | 2.8kb | 2024-11-09 10:39:39 | 2024-11-09 10:39:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int nums[maxn];
int v[maxn];
int prim[maxn],vis[maxn], len;
int sum[maxn],d[maxn];
inline void eular_shai(int n) // n < N
{
for(int i = 2;i <= n;i ++)
{
if(! vis[i])
prim[len ++] = i;
for(int j = 0;j < len && i * prim[j] <= n; j ++)
{
vis[i * prim[j]] = 1;
if(i % prim[j] == 0)
break;
}
}
}
void eular_num(int n)
{
d[1] = 1; //1 特判
for(int i = 2;i <= n;i ++)
{
if(! vis[i])
{
prim[len ++] = i;
sum[i] = 1;
d[i] = 2; //质数的约数只有1和它本身
}
for(int j = 0; j < len && i * prim[j] <= n; j ++)
{
vis[i * prim[j]] = 1;
if(i % prim[j] == 0)
{
sum[i * prim[j]] = sum[i] + 1;
d[i * prim[j]] = d[i] / (sum[i] + 1) * (sum[i] + 2);
break;
}
sum[i * prim[j]] = 1;
d[i * prim[j]] = d[i] * 2;
}
}
}
inline int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int val[maxn<<2];
inline void pushup(int p){
val[p]=gcd(val[p<<1],val[p<<1|1]);
}
inline void build(int p,int l,int r){
if(l==r){
val[p]=v[l];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
inline void update(int p,int l,int r,int np,int nv){
if(l==r){
val[p]=nv;
return;
}
int mid=l+r>>1;
if(np<=mid)update(p<<1,l,mid,np,nv);
else update(p<<1|1,mid+1,r,np,nv);
pushup(p);
}
inline int query(int p,int l,int r,int st,int en){
if(st<=l&&en>=r){
return val[p];
}
int mid=l+r>>1;
int gd=0;
if(st<=mid)gd=gcd(gd,query(p<<1,l,mid,st,en));
if(en>mid)gd=gcd(gd,query(p<<1|1,mid+1,r,st,en));
return gd;
}
void slove(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>nums[i];
v[i]=0;
}
for(int i=2;i<=n;i++){
if(nums[i]<nums[i-1]){
v[i]=i-1;
}
}
build(1,1,n);
if(n==1)cout<<1<<endl;
else cout<<d[query(1,1,n,1,n)]<<'\n';
auto change=[&](int x){
if(nums[x]<nums[x-1]){
update(1,1,n,x,x-1);
}else update(1,1,n,x,0);
};
while(q--){
int np,nv;
cin>>np>>nv;
nums[np]=nv;
change(np);
if(n==1)cout<<1<<endl;
else cout<<d[query(1,1,n,1,n)]<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
cin>>_;
eular_shai(maxn-1);
eular_num(maxn-1);
while(_--)slove();
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 7288kb
input:
1 5 2 4 3 2 6 1 2 5 3 5
output:
1 2 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7136kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 42ms
memory: 11460kb
input:
1 200000 200000 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 ...
result:
wrong answer 2nd lines differ - expected: '200000', found: '160'