QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556611#9245. Bracket SequencezltWA 3ms14192kbC++147.6kb2024-09-10 19:40:152024-09-10 19:40:15

Judging History

This is the latest submission verdict.

  • [2024-09-10 19:40:15]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 14192kb
Show
  • [2024-09-10 19:40:15]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

bool Mst;

const int maxn = 100100;
const ll mod = 998244353;

ll n, m, ans[maxn * 10], a[maxn];
char s[maxn];

struct node {
	int l, r, i, k;
	node(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), i(c), k(d) {}
};

ll f[maxn][42][2], g[maxn][42][2], f1[maxn][42][2][2], g1[maxn][42][2][2], h[maxn][42][2][2];

void dfs(int l, int r, vector<node> q1, vector<node> q2) {
	if (q1.empty() && q2.empty()) {
		return;
	}
	int mid = (l + r) >> 1;
	vector<node> ql1, qm1, qr1, ql2, qm2, qr2;
	for (node u : q1) {
		if (u.r <= mid) {
			ql1.pb(u);
		} else if (u.l > mid) {
			qr1.pb(u);
		} else {
			qm1.pb(u);
		}
	}
	for (node u : q2) {
		if (u.r <= mid) {
			ql2.pb(u);
		} else if (u.l > mid) {
			qr2.pb(u);
		} else {
			qm2.pb(u);
		}
	}
	dfs(l, mid, ql1, ql2);
	dfs(mid + 1, r, qr1, qr2);
	mems(f[mid + 1], 0);
	mems(g[mid], 0);
	mems(f1[mid + 1], 0);
	mems(g1[mid], 0);
	f[mid + 1][0][1] = g[mid][0][0] = 1;
	f1[mid + 1][0][1][0] = g1[mid][0][0][0] = 1;
	for (int i = mid; i >= l; --i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				f[i][j][k] = f[i + 1][j][k];
				f1[i][j][k][0] = f1[i + 1][j][k][0];
				f1[i][j][k][1] = f1[i + 1][j][k][1];
				if (j && k == a[i]) {
					f[i][j][k] = (f[i][j][k] + f[i + 1][j - 1][k ^ 1]) % mod;
					f1[i][j][k][0] = (f1[i][j][k][0] + f1[i + 1][j - 1][k ^ 1][0]) % mod;
					f1[i][j][k][1] = (f1[i][j][k][1] + f1[i + 1][j - 1][k ^ 1][0] * i) % mod;
				}
				// if (l == 1 && r == 3 && f1[i][j][k][0]) {
					// printf("%d %d %d %lld\n", i, j, k, f1[i][j][k][0]);
				// }
			}
		}
	}
	for (int i = mid + 1; i <= r; ++i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				g[i][j][k] = g[i - 1][j][k];
				g1[i][j][k][0] = g1[i - 1][j][k][0];
				g1[i][j][k][1] = g1[i - 1][j][k][1];
				if (j && k == a[i]) {
					g[i][j][k] = (g[i][j][k] + g[i - 1][j - 1][k ^ 1]) % mod;
					g1[i][j][k][0] = (g1[i][j][k][0] + g1[i - 1][j - 1][k ^ 1][0]) % mod;
					g1[i][j][k][1] = (g1[i][j][k][1] + g1[i - 1][j - 1][k ^ 1][0] * i) % mod;
				}
			}
		}
	}
	for (node u : qm1) {
		for (int i = 0; i <= u.k; ++i) {
			ans[u.i] = (ans[u.i] + f[u.l][i][0] * g[u.r][u.k - i][1]) % mod;
		}
	}
	for (node u : qm2) {
		ll v = (mod - 1LL * u.l * u.r % mod - u.l + u.r + mod + 1) % mod;
		for (int i = 0; i <= u.k; ++i) {
			ans[u.i] = (ans[u.i] + f[u.l][i][0] * g[u.r][u.k - i][1] % mod * v) % mod;
			if (i && i < u.k) {
				// if (u.l == 1 && u.r == 3) {
					// printf("%d %lld %lld\n", i, f1[u.l][i][0][1], g1[u.r][u.k - i][1][1]);
				// }
				ans[u.i] = (ans[u.i] + f1[u.l][i][0][1] * g[u.r][u.k - i][1] % mod * (u.r + 1)) % mod;
				ans[u.i] = (ans[u.i] + f[u.l][i][0] * g1[u.r][u.k - i][1][1] % mod * (u.l - 1)) % mod;
				ans[u.i] = (ans[u.i] - f1[u.l][i][0][1] * g1[u.r][u.k - i][1][1] % mod + mod) % mod;
			}
		}
	}
	mems(f[mid + 1], 0);
	mems(g[mid], 0);
	mems(f1[mid + 1], 0);
	mems(g1[mid], 0);
	f[mid + 1][0][0] = g[mid][0][1] = 1;
	f1[mid + 1][0][0][0] = g1[mid][0][1][0] = 1;
	for (int i = mid; i >= l; --i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				f[i][j][k] = f[i + 1][j][k];
				f1[i][j][k][0] = f1[i + 1][j][k][0];
				f1[i][j][k][1] = f1[i + 1][j][k][1];
				if (j && k == a[i]) {
					f[i][j][k] = (f[i][j][k] + f[i + 1][j - 1][k ^ 1]) % mod;
					f1[i][j][k][0] = (f1[i][j][k][0] + f1[i + 1][j - 1][k ^ 1][0]) % mod;
					f1[i][j][k][1] = (f1[i][j][k][1] + f1[i + 1][j - 1][k ^ 1][0] * i) % mod;
				}
			}
		}
	}
	for (int i = mid + 1; i <= r; ++i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				g[i][j][k] = g[i - 1][j][k];
				g1[i][j][k][0] = g1[i - 1][j][k][0];
				g1[i][j][k][1] = g1[i - 1][j][k][1];
				if (j && k == a[i]) {
					g[i][j][k] = (g[i][j][k] + g[i - 1][j - 1][k ^ 1]) % mod;
					g1[i][j][k][0] = (g1[i][j][k][0] + g1[i - 1][j - 1][k ^ 1][0]) % mod;
					g1[i][j][k][1] = (g1[i][j][k][1] + g1[i - 1][j - 1][k ^ 1][0] * i) % mod;
				}
			}
		}
	}
	for (node u : qm1) {
		for (int i = 0; i <= u.k; ++i) {
			ans[u.i] = (ans[u.i] + f[u.l][i][0] * g[u.r][u.k - i][1]) % mod;
		}
	}
	for (node u : qm2) {
		ll v = (mod - 1LL * u.l * u.r % mod - u.l + u.r + mod + 1) % mod;
		for (int i = 0; i <= u.k; ++i) {
			ans[u.i] = (ans[u.i] + f[u.l][i][0] * g[u.r][u.k - i][1] % mod * v) % mod;
			if (i && i < u.k) {
				ans[u.i] = (ans[u.i] + f1[u.l][i][0][1] * g[u.r][u.k - i][1] % mod * (u.r + 1)) % mod;
				ans[u.i] = (ans[u.i] + f[u.l][i][0] * g1[u.r][u.k - i][1][1] % mod * (u.l - 1)) % mod;
				ans[u.i] = (ans[u.i] - f1[u.l][i][0][1] * g1[u.r][u.k - i][1][1] % mod + mod) % mod;
			}
		}
		ans[u.i] = (ans[u.i] + f1[u.l][u.k][0][1] * (u.r + 1) + g1[u.r][u.k][1][1] * (u.l - 1)) % mod;
	}
	mems(f[mid + 1], 0);
	mems(g[mid], 0);
	f[mid + 1][0][0] = g[mid][0][1] = 1;
	for (int i = mid; i >= l; --i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				f[i][j][k] = f[i + 1][j][k];
				if (j && k == a[i]) {
					if (j >= 2) {
						f[i][j][k] = (f[i][j][k] + f[i + 1][j - 1][k ^ 1]) % mod;
					} else {
						f[i][j][k] = (f[i][j][k] + f[i + 1][j - 1][k ^ 1] * i) % mod;
					}
				}
			}
		}
	}
	for (int i = mid + 1; i <= r; ++i) {
		for (int j = 0; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				g[i][j][k] = g[i - 1][j][k];
				if (j && k == a[i]) {
					if (j >= 2) {
						g[i][j][k] = (g[i][j][k] + g[i - 1][j - 1][k ^ 1]) % mod;
					} else {
						g[i][j][k] = (g[i][j][k] + g[i - 1][j - 1][k ^ 1] * i) % mod;
					}
				}
			}
		}
	}
	for (node u : qm2) {
		ans[u.i] = (ans[u.i] + f[u.l][u.k][0] * (u.l - 1) + g[u.r][u.k][1] * (u.r + 1)) % mod;
	}
	mems(h[mid + 1], 0);
	for (int i = mid; i >= l; --i) {
		for (int j = 1; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				h[i][j][k][0] = h[i + 1][j][k][0];
				h[i][j][k][1] = h[i + 1][j][k][1];
				if (k == a[i]) {
					h[i][j][k][0] = (h[i][j][k][0] + h[i + 1][j - 1][k ^ 1][0]) % mod;
					h[i][j][k][1] = (h[i][j][k][1] + h[i + 1][j - 1][k ^ 1][0] * i) % mod;
					if (j == 1 && k) {
						h[i][j][k][0] = (h[i][j][k][0] + i) % mod;
					}
				}
			}
		}
	}
	for (node u : qm2) {
		ans[u.i] = (ans[u.i] - h[u.l][u.k][0][1] + mod) % mod;
	}
	mems(h[mid], 0);
	for (int i = mid + 1; i <= r; ++i) {
		for (int j = 1; j <= 40; ++j) {
			for (int k = 0; k <= 1; ++k) {
				h[i][j][k][0] = h[i - 1][j][k][0];
				h[i][j][k][1] = h[i - 1][j][k][1];
				if (k == a[i]) {
					h[i][j][k][0] = (h[i][j][k][0] + h[i - 1][j - 1][k ^ 1][0]) % mod;
					h[i][j][k][1] = (h[i][j][k][1] + h[i - 1][j - 1][k ^ 1][0] * i) % mod;
					if (j == 1 && !k) {
						h[i][j][k][0] = (h[i][j][k][0] + i) % mod;
					}
				}
			}
		}
	}
	for (node u : qm2) {
		ans[u.i] = (ans[u.i] - h[u.r][u.k][1][1] + mod) % mod;
	}
}

void solve() {
	scanf("%lld%lld%s", &n, &m, s + 1);
	for (int i = 1; i <= n; ++i) {
		a[i] = (s[i] == ')');
	}
	vector<node> q1, q2;
	for (int i = 1, op, l, r, k; i <= m; ++i) {
		scanf("%d%d%d%d", &op, &l, &r, &k);
		if (l == r) {
			return;
		}
		k <<= 1;
		if (op == 1) {
			q1.pb(l, r, i, k);
		} else {
			q2.pb(l, r, i, k);
		}
	}
	dfs(1, n, q1, q2);
	for (int i = 1; i <= m; ++i) {
		printf("%lld\n", ans[i]);
	}
}

bool Med;

int main() {
	fprintf(stderr, "%.2lf MB\n", (&Mst - &Med) / 1048576.);
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 14192kb

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: 3ms
memory: 6144kb

input:

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

output:

result:

wrong answer 1st lines differ - expected: '807252937', found: ''
English 繁體中文 简体中文

伺服器時間: 2025-02-08 23:40:04 | 開源專案