QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726957#9543. Good PartitionsCabbageWA 42ms11460kbC++142.8kb2024-11-09 10:39:392024-11-09 10:39:40

Judging History

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

  • [2024-11-09 10:39:40]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:11460kb
  • [2024-11-09 10:39:39]
  • 提交

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'