QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727123#9543. Good Partitions20225954WA 298ms22772kbC++203.1kb2024-11-09 11:35:562024-11-09 11:36:01

Judging History

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

  • [2024-11-09 11:36:01]
  • 评测
  • 测评结果:WA
  • 用时:298ms
  • 内存:22772kb
  • [2024-11-09 11:35:56]
  • 提交

answer

#include <bits/stdc++.h>
#define db(x) cerr<<#x<<(x)<<"\n"
#define db1(x) cerr<<#x<<(x)<<" "
#define ll long long 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int Mod = 1e9+7;
const int N = 2.1e5;
int n,m,q;
ll a[N],w[N];
const ll inf = 3e10;
ll gd[N<<2];
void pushup(int o){
    gd[o] = __gcd(gd[o<<1],gd[o<<1|1]);
}
void build(int o,int l,int r){
    if(l==r){
        gd[o] =w[l];
        return ;
    }
    int mid = (l+r)>>1;
    build (o<<1,l,mid);
    build (o<<1|1,mid+1,r);
    pushup(o);
}
void upd(int o,int l,int r,int pos,int v){
    if(pos<l||pos>r)return;
    if(l==pos){
        gd[o] = v;
        return ;
    }
    int mid = (l+r)>>1;
    if(pos<=mid)upd(o<<1,l,mid,pos,v);
    else upd(o<<1|1,mid+1,r,pos,v);
    pushup(o);
}
ll que(int o,int l,int r,int s,int t){
    if(s<=l&&r<=t){
        return gd[o];
    }
    int mid =(l+r)>>1;
    ll gd1 =0,gd2 =0;
    if(s<=mid)gd1 = que(o<<1,l,mid,s,t);
    if(t>mid)gd2 = que(o<<1|1,mid+1,r,s,t);
    ll C = __gcd(gd1,gd2);
    return C;

}
void solve()
{
    cin>>n>>q;
    set<int> s;
    s.insert(1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            s.insert(i);
        }
    }
  //  db(s.size());
    for(auto it = s.begin();it!=s.end();++it){
        if(*it==1)continue;
        w[*it] = *it-*prev(it);
    }
    s.insert(n+1);//插入哨兵
    build(1,1,n);
    ll nowgd = gd[1]; 
    auto ok=[&](ll x){
        ll ans =0;
        for(ll i=1;i*i<=x;i++){
            if(x%i==0&&i*i!=x)ans+=2;
            else if(x%i==0)ans++;
        }
        return ans;
    };
   // db(gd[1]);
   a[0] = inf;
	cout<<(gd[1]==0?n:ok(gd[1]))<<"\n";
    for(int i=1;i<=q;i++){
    	ll id,v;cin>>id>>v;
        a[id] =v;
        auto cal = [&](int p){
        	//cout<<"[i,p]"<<i<<" "<<p<<"\n";
            if(s.count(p)){
                // //原来是,现在不是,那么就要更改
              //  cout<<"i = "<<i<<" ";
                if(a[p]>=a[p-1]){
                    auto le = s.lower_bound(p);--le;
                    auto ri = s.upper_bound(p);
                    int lp = *le,rp = *ri;
                    upd(1,1,n,p,0);
                    upd(1,1,n,rp,rp-lp);//右边第一个的左部分区间改变
                    s.erase(p);//删除该地方
                }
                //原来是,现在也是没有影响
            }else if(!s.count(p)){
                //原来不是,现在不是没有影响,但是现在是就有影响了
                if(a[p]<a[p-1]){ //现在是
                    auto le = s.lower_bound(p);--le;
                    auto ri = s.upper_bound(p);
                    upd(1,1,n,p,p-*le);
                    upd(1,1,n,*ri,*ri-p);
                    s.insert(p);
                }   
            }
           // cout<<"s.size()"<<s.size()<<"\n";
        };
    //    cout<<"s.size()"<<s.size()<<"\n";
        cal(id);if(id+1<=n)cal(id+1);
       cout<<(gd[1]==0?n:ok(gd[1]))<<"\n";
    }
}
int main()
{
 	IOS;
    int _;cin>>_;
    while(_--)solve();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7640kb

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: 5676kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 178ms
memory: 11352kb

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
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160...

result:

ok 200001 lines

Test #4:

score: 0
Accepted
time: 165ms
memory: 22772kb

input:

1
200000 200000
200001 200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 1999...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200001 lines

Test #5:

score: 0
Accepted
time: 298ms
memory: 11280kb

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:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 200001 lines

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 5660kb

input:

2
2 2
17017 63462
2 94054
2 13504
8 8
14380 5840 34752 73602 60279 26105 44308 78318
7 8597
2 70671
6 56663
5 90093
5 96853
3 10700
1 76875
6 27325

output:

2
2
1
1
1
2
2
1
1
1
1
1

result:

wrong answer 6th lines differ - expected: '1', found: '2'