QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #759468 | #9543. Good Partitions | yyawdxhp | WA | 293ms | 25724kb | C++20 | 8.6kb | 2024-11-18 09:04:02 | 2024-11-18 09:04:03 |
Judging History
answer
// Problem: I. Good Partitions
// Contest: Codeforces - 2024 ICPC Asia Chengdu Regional Contest (The 3rd Universal Cup. Stage 15: Chengdu)
// URL: https://codeforces.com/gym/105486/problem/I
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
//#define int long long
#define ls root<<1
#define rs root<<1|1
using namespace std;
const int N=2e5+10;
struct SegmentTree{
int l,r,gcd;
int left,right;
int tag;
}tree[N<<3];
long long arr[N<<1];
int L[N<<1],R[N<<1],Len[N<<1];
int cnt[N<<1];
int n,m,k,q;
void pushup(int root)
{
tree[root].gcd=__gcd(tree[ls].gcd,tree[rs].gcd);
// cout<<tree[root].gcd<<' ';
tree[root].left=min(tree[ls].left,tree[rs].left);
tree[root].right=max(tree[ls].right,tree[rs].right);
//if(tree[root].right==n) tree[root].gcd=0;
}
void build(int l,int r,int root)
{
tree[root].l=l,tree[root].r=r;
if(l==r)
{
tree[root].gcd=Len[l];
tree[root].left=L[l];
tree[root].right=R[l];
if(R[l]==n) tree[root].gcd=0;
tree[root].tag=0;
return;
}
int mid=l+r>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(root);
}
void pushdown(int root)
{
if(!tree[root].tag) return;
//if(tree[root].right==n) tree[root].gcd=0;
tree[ls].gcd=tree[root].gcd;
tree[rs].gcd=tree[root].gcd;
tree[ls].left=tree[root].left;
tree[rs].left=tree[root].left;
tree[ls].right=tree[root].right;
tree[rs].right=tree[root].right;
tree[ls].tag=tree[rs].tag=tree[root].tag;
tree[root].tag=0;
}
void Change(int l,int r,int root,int val)
{
if(tree[root].l>=l&&tree[root].r<=r){
//pushdown(root);
tree[root].gcd=val;
if(r==n) tree[root].gcd=0;
tree[root].right=r;
tree[root].left=l;
tree[root].tag=1;
return;
}
pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
if(l<=mid) Change(l,r,ls,val);
if(r>mid) Change(l,r,rs,val);
pushup(root);
}
int Search1(int pos,int root,int f)
{
if(tree[root].l==tree[root].r)
return (f==0?tree[root].left:tree[root].right);
pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
int kk=0;
if(pos<=mid) kk=Search1(pos,ls,f);
if(pos>mid) kk=Search1(pos,rs,f);
return kk;
}
int Query(int l,int r,int root)
{
if(tree[root].l>=l&&tree[root].r<=r){
return tree[root].gcd;
}
pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
int ans=0;
if(l<=mid )ans=__gcd(ans,Query(l,r,ls));
if(r>mid) ans=__gcd(ans,Query(l,r,rs));
return ans;
}
void shuchu(int pos)
{
//cout<<Query(1,n,1)<<' ';
int k=Query(1,n,1);
//cout<<k<<' ';
if(k==0) cout<<n<<'\n';
else
cout<<cnt[k]<<'\n';
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>arr[i];
arr[n+1]=0ll;
for(int i=1;i<=n;i++)
{
int pos=i;
while(pos+1<=n&&arr[pos]<=arr[pos+1]) pos++;
int len=pos-i+1;
for(int j=i;j<=pos;j++)
Len[j]=(pos==n?0ll:len),L[j]=i,R[j]=pos;
i=pos;
}
build(1,n,1);
//arr[n+1]=2e9+1;
//cnt[0]=5;
//cout<<endl;
//cout<<tree[1].gcd<<'\n';
//cout<<Len[1]<<' '<<Len[2]<<' '<<Len[3]<<'\n';
shuchu(1);
while(q--)
{
long long val,pos;
cin>>pos>>val;
long long x=arr[pos-1];
long long y=arr[pos];
long long z=arr[pos+1];
//情况1
if(x>y&&y>z){
if(x>val&&val>z)
{
arr[pos]=val;
//直接输出
shuchu(pos);
}
if(x>val&&val<=z){
if(pos+1<=n){
int rr=Search1(pos+1,1,1);
int len=rr-pos+1;
Change(pos,rr,1,len);
}
arr[pos]=val;
shuchu(pos);
//
}
if(x<=val&&val>z){
if(pos-1>=1){
int ll=Search1(pos-1,1,0);
int len=pos-ll+1;
Change(ll,pos,1,len);
}
arr[pos]=val;
shuchu(pos);
}
if(x<=val&&val<=z){
int ll=Search1(pos-1,1,0);
if(pos-1<=0) ll=1;
int rr=Search1(pos+1,1,1);
if(pos+1>n) rr=n;
int len=rr-ll+1;
Change(ll,rr,1,len);
arr[pos]=val;
shuchu(pos);
}
}
//情况2
if(x>y&&y<=z)
{
if(x>val&&val<=z)
{
arr[pos]=val;
//直接输出
shuchu(pos);
}
if(x>val&&val>z){
if(pos+1<=n){
int rr=Search1(pos+1,1,1);
int len=rr-pos;
Change(pos+1,rr,1,len);
}
Change(pos,pos,1,1);
arr[pos]=val;
shuchu(pos);
//
}
if(x<=val&&val>z){
if(pos-1>0){
int ll=Search1(pos-1,1,0);
int len=pos-ll+1;
Change(ll,pos,1,len);}
if(pos+1<=n){
int rr=Search1(pos+1,1,1);
int len=rr-pos;
Change(pos+1,rr,1,len);
}
arr[pos]=val;
shuchu(pos);
}
if(x<=val&&val<=z){
int ll=Search1(pos-1,1,0);//0表示找左边界
if(pos-1<=0) ll=1;
int rr=Search1(pos,1,1);//1表示找右边界
int len=rr-ll+1;
Change(ll,rr,1,len);
arr[pos]=val;
shuchu(pos);
}
}
//情况3
if(x<=y&&y>z){
if(x>val&&val>z)
{
//直接输出
int ll=Search1(pos-1,1,0);
int len=pos-ll;
//cout<<len<<' ';
Change(ll,pos-1,1,len);
Change(pos,pos,1,1);
arr[pos]=val;
shuchu(pos);
}
if(x>val&&val<=z){
int ll=Search1(pos-1,1,0);
int len=pos-ll;
Change(ll,pos-1,1,len);
int rr=Search1(pos+1,1,1);
len=rr-pos+1;
Change(pos,rr,1,len);
arr[pos]=val;
shuchu(pos);
//
}
if(x<=val&&val>z){
arr[pos]=val;
shuchu(pos);
}
if(x<=val&&val<=z){
int rr=Search1(pos+1,1,1);
int ll=Search1(pos-1,1,0);
int len=rr-ll+1;
Change(ll,rr,1,len);
arr[pos]=val;
shuchu(pos);
}
}
//情况4
if(x<=y&&y<=z){
if(x>val&&val>z)
{
//直接输出
int ll=Search1(pos-1,1,0);
int len=pos-ll;
Change(ll,pos-1,1,len);
int rr=Search1(pos+1,1,1);
len=rr-pos;
Change(pos+1,rr,1,len);
Change(pos,pos,1,1);
arr[pos]=val;
shuchu(pos);
}
if(x>val&&val<=z){
int ll=Search1(pos-1,1,0);
int len=pos-ll;
Change(ll,pos-1,1,len);
int rr=Search1(pos+1,1,1);
len=rr-pos+1;
Change(pos,rr,1,len);
arr[pos]=val;
shuchu(pos);
//
}
if(x<=val&&val>z){
int rr=Search1(pos+1,1,1);
int len=rr-pos;
Change(pos+1,rr,1,len);
int ll=Search1(pos,1,0);
len=pos-ll+1;
Change(ll,pos,1,len);
arr[pos]=val;
shuchu(pos);
}
if(x<=val&&val<=z){
arr[pos]=val;
shuchu(pos);
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int i=1;i<N;i++){
for(int j=1;j<=i/j;j++)
{
if(i%j==0){
cnt[i]++;
if(i/j!=j) cnt[i]++;
}
}
}
int _=1;
cin>>_;
while(_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 217ms
memory: 12632kb
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: 217ms
memory: 12560kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 289ms
memory: 25724kb
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: 293ms
memory: 24868kb
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: 256ms
memory: 25652kb
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: 213ms
memory: 12640kb
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'