QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66348#5014. 复读程度10circle7 121ms17544kbC++142.4kb2022-12-08 11:51:162022-12-08 11:51:18

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:51:18]
  • 评测
  • 测评结果:7
  • 用时:121ms
  • 内存:17544kb
  • [2022-12-08 11:51:16]
  • 提交

answer

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

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

ull read() {
	ull 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 = 4000000007;
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];

mt19937 rnd(20221208 + clock());
ull sum[N][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 = 300, q = 0;
	n = read(), q = read();
	for (int i = 1; i <= n; ++i) s[i] = bool(rnd() % 20) + 'a';
	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];
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			hsh H = h[j] - h[i - 1];
			sum[i][j] = lw[H.l][H.h] * rw[H.l][H.h];
		}
	}
	
	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) {
				ans += sum[l][r];
			}
		}
		cout << ans << '\n';
	}
	
	return 0;
}

详细

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 121ms
memory: 12540kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

15720454042420499810
4058077030882532408
14651762045124606089
4030024243931986061
18033423360813892607
9470601111824364484
3883374861354698625
16650831689368240202
8339028189650687576
2683289915379600554
13133811958066776394
14181220923901262251
18173739360450512256
13142314545999179754
148925491596...

result:

ok 500 lines

Test #2:

score: 0
Accepted
time: 49ms
memory: 12548kb

input:

500 500
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszz...

output:

4843650749197240262
7777110205341291111
533576317536031175
16712994243500559204
9988085877723856684
9644193924482321332
3247342125341043527
18152622312040037224
13045121434804725850
10593529771756855740
13316626648976199221
6181092693273210423
9148547538129213975
9376364571107435561
2140403332478526...

result:

ok 500 lines

Test #3:

score: 0
Accepted
time: 72ms
memory: 17544kb

input:

500 500
aaaaabbaabbabbbaabaabbabbabbbaaabaaaabbbbbbaaabaabbbbbbaabbaaaaababbaaaaabbbbababbabaabbbbbbbbaaaaaaabaabbabbbbaabbaabaaabbbabbaabbbabaabaaaaababbaabbabbbabbababbbaabbabaaabbbbaaabbbabbabaabbabbaaabbaabbabbbbaaaaaababaaaabaababbaabbabbabbbabbaabbbaabbaaababaaabbababbbabaababaabbbbbabbababaab...

output:

841375054012212333
13406426787139944226
6541986259052503362
10583258635957015782
11582649090627508617
4747829250201069768
11571422754704651998
14603866222879735665
8438246043626601023
16155298152184479844
9052925087624568857
18388444310571976215
13304308468056840286
18125780089857220122
363421144082...

result:

ok 500 lines

Test #4:

score: 0
Accepted
time: 65ms
memory: 16244kb

input:

500 500
sulasusulasusulasulasulsulasusulasususulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasusulasusulasusulas...

output:

2320755102639148175
17108462705447992416
6030359132551843296
889683039894413148
10901851555398837076
1991544941914879425
9087724446342520941
5134546535199286414
12947484109492427089
5962550827492657739
4877066450610765849
6699323319072695780
11167645157062070624
13985172887966350800
8075429763917070...

result:

ok 500 lines

Test #5:

score: 0
Accepted
time: 33ms
memory: 10684kb

input:

500 500
bbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrx...

output:

18295637548117042088
6105463594888898313
15681140870484623884
17957090271580958329
11763132903578154240
17769627666201366836
16493946443969420940
12712093409624537595
2436698665645215125
8863273927617841787
5065586857868462806
8771649105206144878
6715985691821336097
8851433094837196039
7055234226266...

result:

ok 500 lines

Test #6:

score: 0
Accepted
time: 78ms
memory: 17120kb

input:

500 500
yyyayyayyyayyayyyayyayyyayyyayyyayyayyyyayyayyyayyyayyayyyayyyayyayyayyyyayyyayyyayyayyayyyayyayyayyyayyayyayyyayyyyyayyayyyyayyayyyayyayyyayyyayyyayyayyyayyayyyyayyyayyayyayyyayyayyyayyyyayyyyayyayyyayyayyayyyayyayyayyyyayyayyyayyayyayyyayyyyayyayyayyyayyayyayyyayyayyayyyyayyyayyyayyyyayyay...

output:

6159560444195180556
5294852391541430076
6195718271241091926
7959984071139675340
1598729415848168155
4879964117998052348
2279721248493220290
2026655128556749470
9803272548967597498
1028236064772678471
5410852487707111065
3600180224455323043
60239358603452318
2179897463397058094
16626503365867372202
3...

result:

ok 500 lines

Test #7:

score: 0
Accepted
time: 82ms
memory: 15728kb

input:

500 500
fffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffxfqifffnmogfffxfqifffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqifffffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqifffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfff...

output:

6263422992304461664
10533199195660359295
11930245273187149005
380050211417129795
8399013088311259527
7005867409130681392
6872331929648615383
11661502418569897193
18027795221888639599
8932010711134684820
6331436398298306214
14599171184201697655
16632037523890780117
10373998601812781913
16089838760431...

result:

ok 500 lines

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #8:

score: 0
Time Limit Exceeded

input:

5000 5000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:


result:


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%