QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #551270 | #9245. Bracket Sequence | ucup-team3510# | WA | 704ms | 128600kb | C++14 | 4.4kb | 2024-09-07 16:13:59 | 2024-09-07 16:14:00 |
Judging History
answer
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const unsigned int mod=998244353;
inline void Add(int &x,int y)
{
x+=y,x=x<mod?x:x-mod;
}
int n,m,ans[1000010];
char s[100010];
struct question
{
int l,r,k,id;
};
vector<question> q[(1<<17)+10][2];
inline void add(bool op,int L,int R,int k,int id)
{
int l=1,r=n,p=1;
while(1)
{
int mid=l+r>>1;
if(R<mid)
{
r=mid,p<<=1;
continue;
}
if(L>mid+1)
{
l=mid+1,p=(p<<1)|1;
continue;
}
q[p][op].push_back({L,R,k,id});
break;
}
}
void solve(int l,int r,int p)
{
if(l==r)
{
return;
}
int mid=l+r>>1;
static int f[100010][21][2][2];
memset(f[mid+1],0,sizeof(f[mid+1]));
f[mid+1][0][0][0]=1;
for(int i=mid;i>=l;i--)
{
memcpy(f[i],f[i+1],sizeof(f[i]));
for(int j=0;j<=20;j++)
{
for(int k=0;k<2;k++)
{
for(int l=0;l<2;l++)
{
int v=f[i+1][j][k][l];
if(v)
{
if(s[i]=='(')
{
if(!j&&!k&&!l)
{
Add(f[i][0][0][1],v);
}
if(j<20&&k)
{
Add(f[i][j+1][0][l],v);
}
}
else
{
if(j<20&&!k)
{
Add(f[i][j][1][l],v);
}
}
}
}
}
}
}
static int g[100010][21][2][2];
memset(g[mid],0,sizeof(g[mid]));
g[mid][0][0][0]=1;
for(int i=mid+1;i<=r;i++)
{
memcpy(g[i],g[i-1],sizeof(g[i]));
for(int j=0;j<=20;j++)
{
for(int k=0;k<2;k++)
{
for(int l=0;l<2;l++)
{
int v=g[i-1][j][k][l];
if(v)
{
if(s[i]==')')
{
if(!j&&!k&&!l)
{
Add(g[i][0][0][1],v);
}
if(j<20&&k)
{
Add(g[i][j+1][0][l],v);
}
}
else
{
if(j<20&&!k)
{
Add(g[i][j][1][l],v);
}
}
}
}
}
}
}
for(int i=0;i<q[p][0].size();i++)
{
int l=q[p][0][i].l,r=q[p][0][i].r,k=q[p][0][i].k;
int &Ans=ans[q[p][0][i].id];
for(int j=0;j<=k;j++)
{
Ans=(Ans+(long long)
f[l][j][0][0]*g[r][k-j][0][0])%mod;
if(j<k)
{
Ans=(Ans+(long long)
f[l][j][0][1]*g[r][k-1-j][0][1])%mod;
}
}
}
for(int i=mid;i>=l;i--)
{
for(int j=0;j<=20;j++)
{
Add(f[i][j][0][0],f[i+1][j][0][0]);
Add(f[i][j][0][1],f[i+1][j][0][1]);
}
}
for(int i=mid+1;i<=r;i++)
{
for(int j=0;j<=20;j++)
{
Add(g[i][j][0][0],g[i-1][j][0][0]);
Add(g[i][j][0][1],g[i-1][j][0][1]);
}
}
static int F[100010][21][2];
memset(F[mid+1],0,sizeof(F[mid+1]));
F[mid+1][0][0]=1;
for(int i=mid;i>=l;i--)
{
memcpy(F[i],F[i+1],sizeof(F[i]));
for(int j=0;j<=20;j++)
{
for(int k=0;k<2;k++)
{
int v=F[i+1][j][k];
if(v)
{
if(s[i]=='(')
{
if(j<20&&k)
{
Add(F[i][j+1][0],v);
}
}
else
{
if(j<20&&!k)
{
if(j)
{
Add(F[i][j][1],v);
}
else
{
Add(F[i][j][1],mid-i);
}
}
}
}
}
}
}
static int G[100010][21][2];
memset(G[mid],0,sizeof(G[mid]));
G[mid][0][0]=1;
for(int i=mid;i>=l;i--)
{
memcpy(G[i],G[i-1],sizeof(G[i]));
for(int j=0;j<=20;j++)
{
for(int k=0;k<2;k++)
{
int v=G[i-1][j][k];
if(v)
{
if(s[i]==')')
{
if(j<20&&k)
{
Add(G[i][j+1][0],v);
}
}
else
{
if(j<20&&!k)
{
if(j)
{
Add(G[i][j][1],v);
}
else
{
Add(G[i][j][1],i-mid-1);
}
}
}
}
}
}
}
for(int i=mid;i>=l;i--)
{
for(int j=1;j<=20;j++)
{
Add(F[i][j][0],F[i+1][j][0]);
}
}
for(int i=mid+1;i<=r;i++)
{
for(int j=1;j<=20;j++)
{
Add(G[i][j][0],G[i-1][j][0]);
}
}
for(int i=0;i<q[p][1].size();i++)
{
int l=q[p][1][i].l,r=q[p][1][i].r,k=q[p][1][i].k;
int &Ans=ans[q[p][1][i].id];
for(int j=0;j<=k;j++)
{
Ans=(Ans+(long long)
f[l][j][0][0]*g[r][k-j][0][0])%mod;
if(j<k)
{
Ans=(Ans+(long long)
f[l][j][0][1]*g[r][k-1-j][0][1])%mod;
}
}
Add(Ans,F[l][k][0]);
Add(Ans,G[r][k][0]);
}
solve(l,mid,p<<1);
solve(mid+1,r,(p<<1)|1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s+1;
for(int i=1,op,l,r,k;i<=m;i++)
{
cin>>op>>l>>r>>k;
add(op-1,l,r,k,i);
}
solve(1,n,1);
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18472kb
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: 704ms
memory: 128600kb
input:
100000 1000000 )())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...
output:
807252937 606928536 88031079 122104482 597950507 716633829 810056267 719234156 392529556 736028324 426329153 576581877 315566541 444655931 76394527 216715407 31336797 926955022 529925464 302716489 498728925 1522883 192687717 78253278 690761534 503000238 605305965 33700395 340780822 88050137 23962861...
result:
wrong answer 2nd lines differ - expected: '333653009', found: '606928536'