QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355312 | #6511. Balancing Sequences | ucup-team173# | WA | 16ms | 263248kb | C++20 | 3.4kb | 2024-03-16 15:44:06 | 2024-03-16 15:44:06 |
Judging History
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)