QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726830#9543. Good PartitionsCabbageWA 176ms8248kbC++143.0kb2024-11-09 09:19:582024-11-09 09:19:59

Judging History

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

  • [2024-11-09 09:19:59]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:8248kb
  • [2024-11-09 09:19:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int nums[maxn];
int v[maxn];
struct Seg{
    int val[maxn<<2];
    void pushup(int p){
        val[p]=__gcd(val[p<<1],val[p<<1|1]);
    }
    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);
    }
    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);
    }
    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;
    }
}T;
void slove(){
    int n,q;
    cin>>n>>q;
    memset(v,0,sizeof v);
    for(int i=1;i<=n;i++)cin>>nums[i];
    set<int> s;
    s.insert(0);
    s.insert(1);
    for(int i=2;i<=n;i++){
        if(nums[i]<nums[i-1]){
            s.insert(i);
            auto le=lower_bound(s.begin(),s.end(),i);
            le--;
            v[i]=(i-*le);
        }
    }
    T.build(1,1,n);
    auto change=[&](int x){
        if(nums[x]<nums[x-1]){
            //如果改变后形成了新逆转点
            if(!s.count(x)){
                auto le=lower_bound(s.begin(),s.end(),x);
                le--;
                auto ri=upper_bound(s.begin(),s.end(),x);
                T.update(1,1,n,x,x-*le);
                v[x]=x-*le;
                if(ri!=s.end()){
                    T.update(1,1,n,*ri,*ri-x);
                    v[*ri]=*ri-x;
                }
                s.insert(x);
            }
        }else{
            //如果改变后不是逆转点了
            if(s.count(x)){
                auto le=lower_bound(s.begin(),s.end(),x);
                le--;
                auto ri=upper_bound(s.begin(),s.end(),x);
                if(ri!=s.end()){
                    T.update(1,1,n,*ri,*ri-*le);
                    v[*ri]=*ri-*le;
                }
                T.update(1,1,n,x,0);
                v[x]=0;
                s.erase(x);
            }
        }
    };
    auto ans=[&](int x){
        int res=0;
        for(int i=1;i*i<=x;i++){
            if(x%i==0){
                if(i*i!=x)res+=2;
                else res++;
            }
        }
        return res;
    };
    if(n!=1)cout<<T.query(1,1,n,1,n)<<endl;
    else cout<<1<<endl;
    while(q--){
        int np,nv;
        cin>>np>>nv;
        nums[np]=nv;
        change(np);
        change(np+1);
        if(n!=1)cout<<ans(T.query(1,1,n,1,n))<<endl;
        else cout<<1<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)slove();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4364kb

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: 1ms
memory: 5680kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: -100
Wrong Answer
time: 176ms
memory: 8248kb

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:

166320
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160
0
160...

result:

wrong answer 1st lines differ - expected: '160', found: '166320'