QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#828407	#9245. Bracket Sequence	Nityacke	ML	2ms	7920kb	C++20	2.1kb	2024-12-23 16:30:06	2024-12-23 16:30:20

Judging History

This is the latest submission verdict.

[2024-12-23 16:30:20]
Judged

Verdict: ML
Time: 2ms
Memory: 7920kb

Show

[2024-12-23 16:30:06]
Submitted

answer

#include<bits/stdc++.h>
#define pb push_back
#define Qry array<int,5>
using namespace std;
const int N=1e5+5,K=45,H=998244353;
int n,m,a[N],ans[N*10],f[N][K][2],g[N][K][2];
inline void add(int &x,int y){if((x+=y)>=H) x-=H;}
inline void clear(int l,int r){
	for(int i=l;i<=r;++i)
		for(int j=0;j<=40;++j) for(int c=0;c<2;++c) f[i][j][c]=g[i][j][c]=0;
}
inline void dp(int l,int mid,int r){
	for(int i=mid;i>=l;--i)
		for(int j=0;j<=40;++j)
			add(f[i][j+1][a[i]],f[i+1][j][!a[i]]),add(f[i][j][0],f[i+1][j][0]),add(f[i][j][1],f[i+1][j][1]);
	for(int i=mid+1;i<=r;++i)
		for(int j=0;j<=40;++j)
			add(g[i][j+1][a[i]],g[i-1][j][!a[i]]),add(g[i][j][0],g[i-1][j][0]),add(g[i][j][1],g[i-1][j][1]);
}
inline void Pre(int l,int mid,int r){
	for(int i=mid;i>=l;--i)
		for(int j=0;j<=40;++j) for(auto c:{0,1}) add(f[i][j][c],f[i+1][j][c]);
	for(int i=mid+1;i<=r;++i)
		for(int j=0;j<=40;++j) for(auto c:{0,1}) add(g[i][j][c],g[i-1][j][c]);
}
inline void solve(int l,int r,vector<Qry>vec){
	if(!vec.size()) return;
	vector<Qry>ql,qr,now;
	int mid=(l+r)>>1;
	for(auto v:vec)
		if(v[2]<=mid) ql.pb(v);
		else if(v[1]>mid) qr.pb(v);
		else now.pb(v);
	solve(l,mid,ql),solve(mid+1,r,qr),vec=now;
	if(!vec.size()) return;
	clear(l,r);
	for(auto c:{0,1}) f[mid+1][0][c]=g[mid][0][c]=1;
	dp(l,mid,r);
	for(auto v:vec) if(v[0]==1){
			int nd=v[3]<<1;
			for(int j=0;j<=nd;++j)
				add(ans[v[4]],1ll*f[v[1]][j][0]*g[v[2]][nd-j][1]%H);
		}
	Pre(l,mid,r);
	for(auto v:vec) if(v[0]==2){
			int nd=v[3]<<1;
			for(int j=0;j<=nd;++j)
				add(ans[v[4]],1ll*f[v[1]][j][0]*g[v[2]][nd-j][1]%H);
		}
	clear(l,r);
	for(int i=mid;i>=l;i--) for(int c:{0,1}) f[i][0][c]=1;
	for(int i=mid+1;i<=r;i++) for(int c:{0,1}) g[i][0][c]=1;
	dp(l,mid,r),Pre(l,mid,r);
	for(auto v:vec)
		if(v[0]==2) add(ans[v[4]],f[v[1]][v[3]<<1][0]),add(ans[v[4]],f[v[2]][v[3]<<1][1]);
}
vector<Qry>Q;
char C;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m,Q.resize(m);
	for(int i=1;i<=n;++i) cin>>C,a[i]=(C==')');
	for(int op,l,r,k,i=0;i<m;++i) cin>>op>>l>>r>>k,Q[i]={op,l,r,k,i};
	solve(1,n,Q);
	for(int i=0;i<m;++i) cout<<ans[i]<<"\n";
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 7920kb

input:

output:

result:

ok 20 lines

Test #2:

score: -100

Memory Limit Exceeded

input:

100000 1000000
)())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...