QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291188#2996. 字符串问题MoRanSky100 ✓2278ms396828kbC++233.5kb2023-12-26 05:17:292023-12-26 05:17:30

Judging History

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

  • [2023-12-26 05:17:30]
  • 评测
  • 测评结果:100
  • 用时:2278ms
  • 内存:396828kb
  • [2023-12-26 05:17:29]
  • 提交

answer

// Skyqwq
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef map<int, int>::iterator MIT;
const int N = 2e5 + 5, S = N * 6, M = N * 7, L = 19;

int n, m, na, nb, La[N], Ra[N], Lb[N], Rb[N], fa[S][L], dep[S], q[S], in[S];
LL f[S], w[S];

char s[N];

map<int, int> mp[S];

int head[S], numE = 0, cnt;

struct E{
	int next, v;
} e[M];

int last = 1, idx = 1, pos[N];

vector<int> g[S];

struct SAM{
	int ch[26], link, len;
} t[S];

void inline insert(int c, int i) {
	int x = ++idx, p = last; t[x].len = t[p].len + 1; pos[i] = x;
	while (p && !t[p].ch[c]) t[p].ch[c] = x, p = t[p].link;
	if (!p) t[x].link = 1;
	else {
		int q = t[p].ch[c];
		if (t[p].len + 1 == t[q].len) t[x].link = q;
		else {
			int y = ++idx; t[y] = t[q], t[y].len = t[p].len + 1;
			while (p && t[p].ch[c] == q) t[p].ch[c] = y, p = t[p].link;
			t[q].link = t[x].link = y;
		}
	}
	last = x;
}

void inline add(int u, int v) {
	in[v]++;
	e[++numE] = (E) { head[u], v };
	head[u] = numE;
}

void inline clear() {
	for (int i = 1; i <= n; i++) pos[i] = 0;
	for (int i = 0; i <= na + nb + cnt; i++) {
		dep[i] = 0, head[i] = 0;
		g[i].clear(), mp[i].clear(), in[i] = 0;
		for (int j = 0; j < 26; j++) t[i].ch[j] = 0;
		t[i].len = t[i].link = 0;
		for (int j = 0; j < L; j++) fa[i][j] = 0;
	}
	numE = 0; last = 1, idx = 1;
}

void dfs(int u) {
	for (int i = 1; i < L; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == fa[u][0]) continue;
		dep[v] = dep[u] + 1, fa[v][0] = u;
		dfs(v);
	}
}

int inline get(int l, int r) {
	int x = pos[r], len = r - l + 1;
	for (int i = L - 1; ~i; i--) 
		if (len <= t[fa[x][i]].len) x = fa[x][i];
	if (!mp[x].count(len)) mp[x][len] = ++cnt;
	return mp[x][len];
}

void inline change(int &x, int &y) {
	int t1 = n - y + 1, t2 = n - x + 1;
	x = t1, y = t2;
}

LL inline toposort() {
	int hh = 1, tt = 0; LL res = 0;
	for (int i = 1; i <= na + nb + cnt; i++) {
		if (!in[i]) q[++tt] = i;
		f[i] = w[i] = i <= na ? Ra[i] - La[i] + 1 : 0;
	}
	while (hh <= tt) {
		int u = q[hh++]; res = max(res, f[u]);
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			f[v] = max(f[v], f[u] + w[v]);
			if (--in[v] == 0) q[++tt] = v;
		}
	}
	if (tt != na + nb + cnt) return -1;
	return res;
}

int main() {
	int T; scanf("%d", &T);
	for (int ca = 1; ca <= T; ca++) {
		scanf("%s%d", s + 1, &na); n = strlen(s + 1);
		reverse(s + 1, s + 1 + n);
		for (int i = 1; i <= n; i++) insert(s[i] - 'a', i);
		for (int i = 1; i <= idx; i++) mp[i][t[i].len] = i;
		cnt = idx;
		for (int i = 2; i <= idx; i++) g[t[i].link].push_back(i);
		dfs(1);
		for (int i = 1; i <= na; i++) scanf("%d%d", La + i, Ra + i), change(La[i], Ra[i]);
		scanf("%d", &nb);
		for (int i = 1; i <= nb; i++) scanf("%d%d", Lb + i, Rb + i), change(Lb[i], Rb[i]);
		for (int i = 1; i <= na; i++) add(get(La[i], Ra[i]) + na + nb, i);
		for (int i = 1; i <= nb; i++) add(i + na, get(Lb[i], Rb[i]) + na + nb);
		for (int i = 1; i <= idx; i++) {
			int t = -1;
			if (mp[fa[i][0]].size()) t = (--mp[fa[i][0]].end()) -> second;
			for (MIT it = mp[i].begin(); it != mp[i].end(); it++) {
				if (t != -1) add(t + na + nb, it -> second + na + nb);
				t = it -> second;
			}
		}
		scanf("%d", &m);
		while (m--) {
			int x, y; scanf("%d%d", &x, &y);
			add(x, na + y);
		}
		printf("%lld\n", toposort());
		clear();
	}
	return 0;
}

詳細信息

Test #1:

score: 10
Accepted
time: 30ms
memory: 110032kb

input:

39
feyqwovxbehhhyykvnpmukgbaxtvurzvefkdodefqcefjeargabaccbawcaccbcbbbaacbfabbabaqacabaabbbbacczabcbabcbacacccapacabbccabaabaaacaaacabbcacbbbbbccbcabcccbbabbbacabbccaabababcabaaabbcbcbcabaccacaabaaaaaaaacbcacccbcbbbbaababcaccbbcabbcccbcccacabbcabacbcbbbaacabbabababcbcabcacbaccbcaaaaabbaacacbccacbacab...

output:

-1
-1
-1
190
-1
164
166
124
143
-1
-1
-1
77
-1
130
128
-1
93
-1
141
155
166
90
-1
126
140
157
147
172
211
173
125
-1
135
-1
-1
150
-1
94

result:

ok 39 lines

Test #2:

score: 10
Accepted
time: 475ms
memory: 186008kb

input:

30
glhfabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaabglhfabbaabbabaababbabaabbaababbaa...

output:

520
11636
8316
-1
396669
-1
350903
-1
15905
72960
36798
17488
42761
39434
26279
32797
-1
32042
-1
27408
19823
24985
32314
-1
37908
31169
22963
39115
28035
47216

result:

ok 30 lines

Test #3:

score: 10
Accepted
time: 462ms
memory: 186072kb

input:

29
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

-1
7400
11278
-1
-1
208692
474219
227871
33959
46213
44661
16603
32041
38509
31999
36344
16953
14347
44406
38540
16170
14572
15839
29668
25281
50172
-1
-1
-1

result:

ok 29 lines

Test #4:

score: 10
Accepted
time: 929ms
memory: 235480kb

input:

10
hwjtltzilyfsusnhgiiocavujiaordjtgmtvfacaoiwrypgvtpcjddonbncqqwbxnoajiysnijzabynekoyknnlhvnfjtzcjmfmaknqprfuvtajlbgyqiybpohfvvtarjmuersynvppjrrdapgclodkbvzueeasqsyqhtbwmqauxjcqnsacpvnhsexsswvefricteedsenmlixgvozclwsvjeijvmwmlybjrlafknhdbgpirovdddrwkyiiwwarkpcbezbrjutwwporlbngviuhurixhqdlageggeauvz...

output:

-1
-1
-1
199914
199929
199873
-1
199905
-1
199957

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 1200ms
memory: 276336kb

input:

51
wwwgrmskhauxztuyflowbcqctyplrcbyqyqptvnsptwnyptlymjrlglmhevhpiazuryqespxskopjkadwcbxeidlvipouzfdpnbwafvkgxvlsqsekspqftipymojxlwgprreagzbeasigcjbudvnzsnvohnuplllsnyucexakvbxbmxodrcpdhhyawbolwxlyifppayhzzeckibvvlpogxqmucyuzcahvnvoskwinuuqkkwmqqqxfkorzsiwrripxkjvstxbxhmkwwwqyjqjqicphgajewwxqwrvticen...

output:

94331
104718
96829
106368
-1
7495
3097
-1
-1
-1
-1
369
-1
384
-1
-1
-1
-1
128
-1
353
-1
335
-1
-1
111
-1
176
-1
-1
242
-1
-1
-1
-1
311
-1
-1
302
-1
-1
-1
-1
-1
-1
315
171
-1
308
-1
-1

result:

ok 51 lines

Test #6:

score: 10
Accepted
time: 1258ms
memory: 281164kb

input:

44
ixhuitywihrcjeipcicrhkxxolouyjwnlcbgjqleiyxlrjsgupohhyvlmtaqesonoyrhsyulmtbegrqvtvsfxjnjlgjekqyaqzpfmwyouavubxmcxrzhjabaodkawfkajdsraxcptqsyleeymvfxqkdrjktonfezutfkkzfxcrtqolaahthrbulyjaffspdotvgdbjvennbintmrqnkjqndrilksjrakgkhcglfmanjplbhedebdmkgxolwrpydcsstptezgxrjgyirrtwxywwoyrghrztlpzkeprwhvm...

output:

110089
98880
100758
104230
-1
4378
4495
4898
-1
-1
-1
-1
282
263
196
-1
-1
-1
-1
421
283
303
224
-1
-1
-1
223
331
-1
-1
-1
181
336
-1
-1
-1
469
-1
252
-1
-1
-1
-1
355

result:

ok 44 lines

Test #7:

score: 10
Accepted
time: 1741ms
memory: 318476kb

input:

100
glhfabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabba...

output:

131080
213027672
200450529
201721754
203425350
59784340
62075296
59178758
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
55
-1
-1
107
15
-1
-1
-1
54
-1
-1
-1
-1
-1
-1
15
61
107
86
131
30
-1
-1
-1
-1
39
85
44
26
-1
-1
-1
26
-1
-1
35
110
28
-1
-1
-1
-1
16
-1
-1
-1
68
91
59
-1
-1
-1
-1
111
86
-1
-1
-1
85
-1...

result:

ok 100 lines

Test #8:

score: 10
Accepted
time: 1681ms
memory: 316752kb

input:

100
hggafwsdmxivpnfcjwubzgvaomzilopymnekzlqijbtgujdxpwowbkciohxtkjgmrodlbqsjfnxnynzexbndxukjegrfyiuvktvzxaidfvvgxqwhxxwroprmrtxmbhrulqzerqehjmxzthuirnwhuswqnhysgbjwrbadqraltvkkbbnkfdjyvwuvszcgooizqtjwkbzzosnoututkmeqbynrbbhbjliveufgbfjnwsucnopjdkcfxpcjoptbwgmordieneuaduynfxddisexmcnbinmeyeolobrmfdqz...

output:

-1
208905485
205523915
202863858
206244046
60152261
59695786
63478009
-1
-1
-1
-1
-1
-1
97
-1
-1
-1
25
10
-1
-1
-1
-1
-1
16
-1
112
-1
185
46
26
-1
-1
61
-1
-1
-1
-1
-1
142
-1
-1
-1
35
93
-1
55
-1
-1
71
46
-1
35
-1
-1
-1
10
36
-1
-1
-1
-1
-1
68
74
-1
-1
-1
-1
5
-1
-1
56
-1
-1
-1
-1
-1
-1
14
-1
-1
-1
...

result:

ok 100 lines

Test #9:

score: 10
Accepted
time: 2189ms
memory: 395948kb

input:

100
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

20000100000
62516258
58379078
203874157
200936649
650929
-1
1666983
96590
106367
136970
83485
-1
106132
98111
60799
93680
55617
1076
457
413
602
303
436
419
104
325
-1
494
202
-1
288
-1
429
600
324
286
370
390
477
272
627
495
1319
671
509
208
280
184
71
537
407
380
452
327
-1
773
205
247
-1
430
441
...

result:

ok 100 lines

Test #10:

score: 10
Accepted
time: 2278ms
memory: 396828kb

input:

100
boicmuspttnwpilgnszaafnuxghguuqaxdoeoispntpabpmhtozzqzzzmzzzzzzzzzzzrzzzzzzzzzzzzzzzzzzxzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzznzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

19570070095
56191677
57572613
201905229
201099444
689056
-1
-1
140456
94558
53299
112449
62781
74284
-1
-1
57230
-1
148
548
-1
666
651
-1
305
412
616
592
291
235
463
253
461
-1
621
168
-1
808
-1
560
134
354
215
88
226
548
169
570
663
302
-1
115
234
299
171
525
600
549
170
347
414
300
461
313
-1
442
...

result:

ok 100 lines

Extra Test:

score: 0
Extra Test Passed