QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #587085 | #9245. Bracket Sequence | vme50 | WA | 617ms | 185208kb | C++17 | 2.3kb | 2024-09-24 17:30:51 | 2024-09-24 17:30:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)/2)
#define eb emplace_back
const int N=1e5+5,M=1e6+5,C=45,MOD=998244353;
int n,m,nw,ans[M];char a[N];
int dpl1[N][C],dpr1[N][C],dpl2[N][C],dpr2[N][C],dpl3[N][C],dpr3[N][C];
struct Query {int op,l,r,x,id;};vector<Query> q;
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=(x+y)%MOD;}
int W1(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
void slv(int l,int r,vector<Query> q)
{
if(l==r) return;vector<Query> q1,q2,q3;
for(auto i:q) if(i.r<=mid) q1.eb(i);else if(i.l>mid) q2.eb(i);else q3.eb(i);
fill(dpl1[mid+1],dpl1[mid+1]+41,0);fill(dpl2[mid+1],dpl2[mid+1]+41,0);
fill(dpl3[mid+1],dpl3[mid+1]+41,0);
for(int i=mid;i>=l;--i)
{
for(int j=1;j<=40;++j)
dpl1[i][j]=W1(dpl1[i+1][j],dpl1[i+1][j-1]),
dpl2[i][j]=W1(dpl2[i+1][j],dpl2[i+1][j-1]),
dpl3[i][j]=W1(dpl3[i+1][j],dpl3[i+1][j-1]);
if(a[i]==')') W(dpl1[i][1],1),W(dpl2[i][1],mid-i+1);else W(dpl3[i][1],1);
}
fill(dpr1[mid],dpr1[mid]+41,0);fill(dpr2[mid],dpr2[mid]+41,0);
fill(dpr3[mid],dpr3[mid]+41,0);
for(int i=mid+1;i<=r;++i)
{
for(int j=1;j<=40;++j)
dpr1[i][j]=W1(dpr1[i-1][j],dpr1[i-1][j-1]),
dpr2[i][j]=W1(dpr2[i-1][j],dpr2[i-1][j-1]),
dpr3[i][j]=W1(dpr3[i-1][j],dpr3[i-1][j-1]);
if(a[i]=='(') W(dpr1[i][1],1),W(dpr2[i][1],i-mid);else W(dpr3[i][1],1);
}
for(auto [op,l1,r1,x,id]:q3) if(op==1)
{
W(ans[id],dpl1[l1][x*2]);W(ans[id],dpr1[r1][x*2]);
for(int i=1;i<x*2;++i)
W(ans[id],i&1?1ll*dpl3[l1][i]*dpr3[r1][x*2-i]:1ll*dpl1[l1][i]*dpr1[r1][x*2-i]);
}
for(int i=mid;i>=l;--i) for(int j=0;j<=40;++j)
W(dpl1[i][j],dpl1[i+1][j]),W(dpl2[i][j],dpl2[i+1][j]),W(dpl3[i][j],dpl3[i+1][j]);
for(int i=mid+1;i<=r;++i) for(int j=0;j<=40;++j)
W(dpr1[i][j],dpr1[i-1][j]),W(dpr2[i][j],dpr2[i-1][j]),W(dpr3[i][j],dpr3[i-1][j]);
for(auto [op,l1,r1,x,id]:q3) if(op==2)
{
W(ans[id],dpl2[l1][x*2]+1ll*dpl1[l1][x*2]*(r1-mid));
W(ans[id],dpr2[r1][x*2]+1ll*dpr1[r1][x*2]*(mid-l1+1));
for(int i=1;i<x*2;++i)
W(ans[id],i&1?1ll*dpl3[l1][i]*dpr3[r1][x*2-i]:1ll*dpl1[l1][i]*dpr1[r1][x*2-i]);
}
slv(l,mid,q1);slv(mid+1,r,q2);
}
int main()
{
scanf("%d %d %s",&n,&m,a+1);q.resize(m);
for(auto &[op,l,r,x,id]:q) scanf("%d %d %d %d",&op,&l,&r,&x),id=nw++;
slv(1,n,q);for(int i=0;i<m;++i) printf("%d\n",ans[i]);return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 16308kb
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: 617ms
memory: 185208kb
input:
100000 1000000 )())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...
output:
503988146 372158186 528592402 920770021 673677114 858095504 187076796 117287628 927245523 977378486 237603009 607137422 625313614 594813977 231499137 193648368 944272145 817666223 310162608 665437918 217851405 2638337 37393248 418961210 116226743 338546780 737036395 599987883 220450881 88091464 3282...
result:
wrong answer 1st lines differ - expected: '807252937', found: '503988146'