QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66316#5014. 复读程度czxb20 59ms14364kbC++142.1kb2022-12-08 11:38:052022-12-08 11:38:08

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:38:08]
  • 评测
  • 测评结果:0
  • 用时:59ms
  • 内存:14364kb
  • [2022-12-08 11:38:05]
  • 提交

answer

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

using ul = unsigned long long;
using ll = long long;
using l3 = __int128_t;
const int N = 5100;
const ul M = 1000000007ll * 1000000009;
#define IO(a) cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define F(i, a, b) for (int i = (a), iee = (b); i <= iee; i++)

int n, q;
char s[N];
ul wl[N], wr[N], w[N][N];
ul a[N][N];
unordered_map<ul, ul> sl, sr;

int lcp(int x, int y) {
	int l = 0, r = n - max(x, y), ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (a[x][x + m] == a[y][y + m])
			ans = m, l = m + 1;
		else
			r = m - 1;
	}
	return ans + 1;
}
int lcs(int x, int y) {
	int l = 0, r = min(x, y) - 1, ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (a[x - m][x] == a[y - m][y])
			ans = m, l = m + 1;
		else
			r = m - 1;
	}
	return ans + 1;
}
int cpre(int l1, int r1, int l2, int r2) {
	int l = lcp(l1, l2), x = r1 - l1 + 1, y = r2 - l2 + 1;
	if (l < x && l < y) return s[l1 + l] < s[l2 + l];
	if (l >= x && l >= y) return 0;
	return x < y;
}
int csuf(int l1, int r1, int l2, int r2) {
	int l = lcs(r1, r2), x = r1 - l1 + 1, y = r2 - l2 + 1;
	if (l < x && l < y) return s[r1 - l] < s[r2 - l];
	if (l >= x && l >= y) return 0;
	return x < y;
}
int pre[N], suf[N];

int main() {
	IO(b);
	cin >> n >> q >> s + 1;
	assert(n <= 5000 && q <= 5000);
	F(i, 1, n) cin >> wl[i];
	F(i, 1, n) cin >> wr[i];
	F(i, 1, n) F(j, i, n) a[i][j] = ((l3)a[i][j - 1] * 1145141919810 + s[j]) % M;
	F(i, 1, n) F(j, i, n) sl[a[i][j]] += wl[i], sr[a[i][j]] += wr[i];
	F(i, 1, n) F(j, i, n) w[i][j] = sl[a[i][j]] * sr[a[i][j]];
	F(i, 1, n) pre[i] = suf[i] = i;
	//sort(pre + 1, pre + n + 1, [](int x, int y) { return cpre(x, n, y, n); });
	//sort(suf + 1, suf + n + 1, [](int x, int y) { return csuf(1, x, 1, y); });
	F(i, 1, q) {
		int l1, r1, l2, r2;
		ul ans = 0;
		cin >> l1 >> r1 >> l2 >> r2;
		int s1 = r1 - l1, s2 = r2 - l2, len = max(s1, s2);
		F(i, 1, n) if (a[i][i + s1] == a[l1][r1])
			F(j, i + len, n) if (a[j - s2][j] == a[l2][r2])
				ans += w[i][j];
		cout << ans << "\n";
	}
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 59ms
memory: 14364kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

14705470963471828566
9404691893886808658
7876477827418776621
4911997747130591098
12459266956655437694
2382215352625272250
17634555486692251432
2829840596683947526
2359370660838595792
11133070212851528303
10992035823474992344
9604012687255557613
17249373044636030184
15281763373596781575
5032378067398...

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #22:

score: 0
Dangerous Syscalls

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%