QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #551185 | #9245. Bracket Sequence | ucup-team1004# | WA | 1ms | 7928kb | C++14 | 2.7kb | 2024-09-07 15:51:05 | 2024-09-07 15:51:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353,K=40;
struct node{
int op,l,r,k,id;
};
int n,Q,k,f[N][K+2][2],g[N][K+2][2],p[N],ans[N*10];
char str[N];
void Clr(vector<node> &q)
{
vector<node> v;
swap(v,q);
}
void pls(int &a,int b)
{
if((a+=b)>=mod) a-=mod;
}
void clr(int l,int r)
{
for(int i=l;i<=r;i++)
for(int j=0;j<=K;j++)
for(int k=0;k<2;k++)
f[i][j][k]=g[i][j][k]=0;
}
void solve(int l,int r,vector<node> q)
{
if(l==r||q.empty()) return;
int mid=(l+r)>>1;
vector<node> q1,q2,q3;
for(auto k:q) if(k.r<=mid) q1.push_back(k);
else if(k.l>mid) q2.push_back(k);
else q3.push_back(k);
Clr(q);
solve(l,mid,q1),solve(mid+1,r,q2);
for(int i=0;i<2;i++)
f[mid+1][0][i]=g[mid][0][i]=1;
for(int i=mid;i>=l;i--)
for(int j=0;j<=K;j++)
{
pls(f[i][j+1][p[i]],f[i+1][j][p[i]^1]);
pls(f[i][j][0],f[i+1][j][0]);
pls(f[i][j][1],f[i+1][j][1]);
}
for(int i=mid+1;i<=r;i++)
for(int j=0;j<=K;j++)
{
pls(g[i][j+1][p[i]],g[i-1][j][p[i]^1]);
pls(g[i][j][0],g[i-1][j][0]);
pls(g[i][j][1],g[i-1][j][1]);
}
for(auto k:q3)
if(k.op==1)
{
int m=2*k.k;
for(int j=0;j<=m;j++)
pls(ans[k.id],1ll*f[k.l][j][0]*g[k.r][m-j][1]%mod);
}
for(int i=mid;i>=l;i--)
for(int j=0;j<=K;j++)
for(int p=0;p<2;p++)
pls(f[i][j][p],f[i+1][j][p]);
for(int i=mid+1;i<=r;i++)
for(int j=0;j<=K;j++)
for(int p=0;p<2;p++)
pls(g[i][j][p],g[i-1][j][p]);
for(auto k:q3)
if(k.op==2)
{
int m=2*k.k;
for(int j=0;j<=m;j++)
pls(ans[k.id],1ll*f[k.l][j][0]*g[k.r][m-j][1]%mod);
}
clr(l,r);
for(int i=l;i<=mid+1;i++)
for(int j=0;j<2;j++) f[i][0][j]=1;
for(int i=mid;i<r;i++)
for(int j=0;j<2;j++) g[i][0][j]=1;
for(int i=mid;i>=l;i--)
for(int j=0;j<=K;j++)
{
pls(f[i][j+1][p[i]],f[i+1][j][p[i]^1]);
pls(f[i][j][0],f[i+1][j][0]);
pls(f[i][j][1],f[i+1][j][1]);
}
for(int i=mid+1;i<=r;i++)
for(int j=0;j<=K;j++)
{
pls(g[i][j+1][p[i]],g[i-1][j][p[i]^1]);
pls(g[i][j][0],g[i-1][j][0]);
pls(g[i][j][1],g[i-1][j][1]);
}
for(int i=mid;i>=l;i--)
for(int j=0;j<=K;j++)
for(int p=0;p<2;p++)
pls(f[i][j][p],f[i+1][j][p]);
for(int i=mid+1;i<=r;i++)
for(int j=0;j<=K;j++)
for(int p=0;p<2;p++)
pls(g[i][j][p],g[i-1][j][p]);
for(auto k:q3)
if(k.op==2)
{
int m=2*k.k,w=k.id;
pls(ans[w],f[k.l][m][0]);
pls(ans[w],g[k.r][m][1]);
}
clr(l,r);
}
int main()
{
scanf("%d%d%s",&n,&Q,str+1);
for(int i=1;i<=n;i++) p[i]=(str[i]==')');
vector<node> q(Q);
for(int i=0;i<Q;i++)
scanf("%d%d%d%d",&q[i].op,&q[i].l,&q[i].r,&q[i].k),q[i].id=i;
solve(1,n,q);
for(int i=0;i<Q;i++) printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7928kb
input:
5 20 (()() 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 2 3 1 1 2 4 1 1 2 5 1 1 3 4 1 1 3 5 1 1 4 5 1 2 1 3 1 2 1 4 1 2 1 5 1 2 2 3 1 2 2 4 1 2 2 5 1 2 3 5 1 2 4 5 1 1 1 5 2 2 1 5 2
output:
0 2 2 5 1 1 3 0 1 1 3 9 20 1 3 9 3 1 2 3
result:
wrong answer 12th lines differ - expected: '6', found: '9'