QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66294#5014. 复读程度10circle0 2023ms9356kbC++142.1kb2022-12-08 11:23:522022-12-08 11:23:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-08 11:23:55]
  • 评测
  • 测评结果:0
  • 用时:2023ms
  • 内存:9356kb
  • [2022-12-08 11:23:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;

int read() {
	int a = 0, b = 0; char c = getchar();
	while (c < '0' || c > '9') b ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9') a = a * 10 - 48 + c, c = getchar();
	return b ? -a : a;
}

const int N = 5002;
const ull B = 31, mod = 1000000007;
typedef unsigned int uint;


char s[N];
ull pw[N];

inline ull st(ull a) { return a >= mod ? a - mod : a; }
struct hsh {
	ull h;
	int l;
	hsh() { h = l = 0; }
	hsh(char c) { l = 1, h = c - 'a' + 1; }
	hsh(ull H, int L) { h = H, l = L; }
	hsh operator + (const hsh &b) const { return hsh { (h * pw[b.l] + b.h) % mod, l + b.l }; }
	hsh operator - (const hsh &b) const { return hsh { st(h - b.h * pw[l - b.l] % mod + mod), l - b.l }; }
	bool operator < (const hsh &b) const { return l == b.l ? h < b.h : l < b.l; }
	bool operator == (const hsh &b) const { return l == b.l && h == b.h; }
} h[N];
int n, q;
ull wl[N], wr[N];
unordered_map<uint, ull> lw[N], rw[N];

int main() {
//	freopen("b.in", "r", stdin);
//	freopen("b.out", "w", stdout);
	pw[0] = 1; for (int i = 1; i < N; ++i) pw[i] = pw[i - 1] * B % mod;
	n = read(), q = read();
	scanf("%s", s + 1);
	for (int i = 1; i <= n; ++i) h[i] = h[i - 1] + s[i];
	for (int i = 1; i <= n; ++i) wl[i] = read();
	for (int i = 1; i <= n; ++i) wr[i] = read();
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			hsh H = h[j] - h[i - 1];
			lw[H.l][H.h] += wl[i];
			rw[H.l][H.h] += wr[j];
		}
	}
	
	while (q--) {
		int l1 = read(), r1 = read(), l2 = read(), r2 = read();
		int L1 = r1 - l1 + 1, L2 = r2 - l2 + 1, mnl = max(L1, L2);
		hsh H1 = h[r1] - h[l1 - 1], H2 = h[r2] - h[l2 - 1];
		ull ans = 0;
		/*
		static ull sr[N];
		memset(sr, 0, sizeof sr);
		for (int i = n; i >= 1; --i) {
			
		}
		*/
		for (int l = 1; l + mnl - 1 <= n; ++l) if (h[l + L1 - 1] - h[l - 1] == H1) {
			for (int r = l + mnl - 1; r <= n; ++r) if (h[r] - h[r - L2] == H2) {
				hsh H = h[r] - h[l - 1];
				ans += lw[H.l][H.h] * rw[H.l][H.h];
			}
		}
		cout << ans << '\n';
	}
	
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2023ms
memory: 9356kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

16971930800064025954
1069867974370581560
1884748677163251849
14626962775218796685
3753759160157275135
10514383726458565572
5387837738332096385
14192237747365511242
15106305577511884376
14030348307433704618
1467296767574346058
3861081507149429163
11315314773634057600
16303412898216734698
131157272330...

result:

wrong answer 1st lines differ - expected: '15720454042420499810', found: '16971930800064025954'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #22:

score: 0
Runtime Error

input:

100000 100000
zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%