QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355312#6511. Balancing Sequencesucup-team173#WA 16ms263248kbC++203.4kb2024-03-16 15:44:062024-03-16 15:44:06

Judging History

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

  • [2024-03-16 15:44:06]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:263248kb
  • [2024-03-16 15:44:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mod=1e9+9;
int add(int x,int y){
    x+=y;
    return x-=mod?x-mod:x;
}
void adto(int&x,int y){
    x+=y;
    x>=mod?(x-=mod):x;
}
int mul(int x,int y){
    return 1ll*x*y%mod;
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}

const int maxn=5e5+10;


struct mat{
    int a[3][3];
    int r,c;
    mat(){
        r=c=2;
    }
    friend mat operator *(const mat&x,const mat&y){
        mat z;
        memset(z.a,0,sizeof z.a);
        assert(x.c==y.r);
        z.r=x.r;
        z.c=y.c;
        for(int i=0;i<x.r;i++){
            for(int j=0;j<x.c;j++){
                for(int k=0;k<y.c;k++){
                    adto(z.a[i][k],mul(x.a[i][j],y.a[j][k]));
                }
            }
        }
        return z;
    }
    bool eq(const mat&x){
        if(r!=x.r)return 0;
        if(c!=x.c)return 0;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(a[i][j]!=x.a[i][j])return 0;
            }
        }
        return 1;
    }
}sd[3],t[3][maxn<<2],tmp[3],one;
int lz[maxn<<2];
string s;
int n;
int q;
void pd(int i,int k){
    if(k%3==0)return;
    lz[i]+=k,lz[i]%=3;
    for(int j=0;j<2;j++){
        tmp[(j-k+3)%3]=t[j][i];
    }
    for(int j=0;j<2;j++){
        t[j][i]=tmp[j];
    }
    return;
}
void pdd(int i){
    if(lz[i]){
        pd(i<<1,lz[i]);
        pd(i<<1|1,lz[i]);
        lz[i]=0;
    }
}
void bld(int i,int l,int r){
    lz[i]=0;
    if(l==r){
        t[0][i]=sd[s[l]-'0'];
        t[1][i]=sd[(s[l]-'0'+1)%3];
        t[2][i]=sd[(s[l]-'0'+2)%3];
        return;
    }
    int mid=l+r>>1;
    bld(i<<1,l,mid);
    bld(i<<1|1,mid+1,r);
    for(int j=0;j<3;j++)
    t[j][i]=t[j][i<<1]*t[j][i<<1|1];
    return;
}
void mdf(int i,int l,int r,int x,int y,int k){
    if(r<x||y<l||y<x)return;
    if(x<=l&&r<=y)return pd(i,k);
    int mid=l+r>>1;
    pdd(i);
    if(x<=mid)mdf(i<<1,l,mid,x,y,k);
    if(y>mid)mdf(i<<1|1,mid+1,r,x,y,k);
    for(int j=0;j<3;j++)
    t[j][i]=t[j][i<<1]*t[j][i<<1|1];
}
mat qry(int i,int l,int r,int x,int y){
    if(r<x||y<l||y<x)return one;
    if(x<=l&&r<=y)return t[0][i];
    int mid=l+r>>1;
    pdd(i);
    mat ans=one;
    if(x<=mid)ans=ans*qry(i<<1,l,mid,x,y);
    if(y>mid)ans=ans*qry(i<<1|1,mid+1,r,x,y);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q>>s;
    s.insert(s.begin(),' ');
    sd[0].c=sd[0].r=2;
    sd[1].c=sd[1].r=2;
    sd[2].c=sd[2].r=2;
    sd[0].a[0][0]=11;
    sd[0].a[0][1]=mod-12;
    sd[0].a[1][0]=10;
    sd[0].a[1][1]=mod-11;
    sd[1].a[0][0]=7;
    sd[1].a[0][1]=mod-8;
    sd[1].a[1][0]=6;
    sd[1].a[1][1]=mod-7;
    sd[2].a[0][0]=4;
    sd[2].a[0][1]=mod-5;
    sd[2].a[1][0]=3;
    sd[2].a[1][1]=mod-4;
    one.r=one.c=2;
    one.a[0][0]=one.a[1][1]=1;
    bld(1,1,n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)mdf(1,1,n,l,r,1);
        else cout<<(qry(1,1,n,l,r).eq(one)?"Yes\n":"No\n");
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 16ms
memory: 263248kb

input:

2
2
1 2
3 4
4 3
2 1
3
1 2 4
3 5 6
1 2 4
5 3 6

output:

Yes
Yes

result:

wrong output format Expected integer, but "Yes" found (test case 1)