QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #551170 | #9245. Bracket Sequence | ucup-team1004# | WA | 712ms | 126652kb | C++14 | 2.7kb | 2024-09-07 15:47:21 | 2024-09-07 15:47:22 |
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][1]);
pls(ans[w],f[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]);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7900kb
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 6 16 1 2 7 2 1 2 3
result:
ok 20 lines
Test #2:
score: -100
Wrong Answer
time: 712ms
memory: 126652kb
input:
100000 1000000 )())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...
output:
807252937 829890608 763162857 122104482 597950507 624173655 49447025 390597667 392529556 736028324 426329153 45746899 315566541 444655931 76394527 216715407 286200843 254063326 378899437 302716489 498728925 1522883 869146157 78253278 848615832 448994141 605305965 30187019 340780822 960087454 6932240...
result:
wrong answer 2nd lines differ - expected: '333653009', found: '829890608'