QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726830 | #9543. Good Partitions | Cabbage | WA | 176ms | 8248kb | C++14 | 3.0kb | 2024-11-09 09:19:58 | 2024-11-09 09:19:59 |
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];
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'