QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #867376 | #1219. 你的名字 | Gold_Dino | Compile Error | / | / | C++14 | 11.7kb | 2025-01-23 14:55:57 | 2025-01-23 14:55:58 |
Judging History
This is the latest submission verdict.
- [2025-01-23 14:55:58]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-01-23 14:55:57]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
#define info(...) fprintf(stderr, __VA_ARGS__)
using ll_t = long long;
const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
ll_t ret[Q];
int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
int mx[T * 4];
int wt[N], sa[N], satmp[N], *head[N], cnt[N], *las, *cur, rk[N], trk[N * 2], H[N];
int expand(int p, char c)
{
int v = ++tot, x = c - 'a';
len[v] = len[p] + 1;
while (!trie[p][x] && p) trie[p][x] = v, p = fail[p];
int f = trie[p][x];
if (!f || f == v) fail[v] = 1;
else if (len[p] + 1 == len[f]) fail[v] = f;
else
{
int t = ++tot;
fail[t] = fail[f], fail[f] = t, len[t] = len[p] + 1, memcpy(trie[t], trie[f], sizeof(trie[t]));
while (trie[p][x] == f && p) trie[p][x] = t, p = fail[p];
fail[v] = t;
}
return v;
}
void DFS(int u)
{
dfn[u] = ++pdfn, sz[u] = 1;
for (int v : nxt[u]) DFS(v), sz[u] += sz[v];
}
#define ls (v << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
#define LEF ls, l, mid
#define RIG rs, mid + 1, r
#define INIT int v = 1, int l = 1, int r = tot
void modify(int p, int x, INIT)
{
// info("[%d %d]\n", l, r);
mx[v] = x;
if (l == r) return;
if (p <= mid) modify(p, x, LEF);
else modify(p, x, RIG);
}
void query(int L, int R, int &ret, INIT)
{
// info("%d %d [%d %d]\n", L, R, l, r);
if (L <= l && R >= r) return mx[v] && (ret = min(ret, mx[v])), void();
if (L <= mid) query(L, R, ret, LEF);
if (R > mid) query(L, R, ret, RIG);
}
void clr(int *f, int n) { memset(f, 0, sizeof(int) * n); }
void cpy(int *f, int *h, int n) { memcpy(f, h, sizeof(int) * n); }
int main()
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> s >> q, n = (int)s.size();
pos[n + 1] = 1;
for (int i = n; i >= 1; --i) pos[i] = expand(pos[i + 1], s[i - 1]);
// for (int i = 1; i <= n; ++i) for (int x = 0; x < 26; ++x) if (trie[i][x]) info("%d %d %c\n", i, trie[i][x], 'a' + x);
for (int i = 2; i <= tot; ++i) nxt[fail[i]].push_back(i);
DFS(1);
for (int i = 1; i <= q; ++i) cin >> t[i] >> L[i] >> R[i], qs[L[i]].push_back(i);
for (int L = n; L >= 1; --L)
{
modify(dfn[pos[L]], L);
// info("add %d %d\n", dfn[pos[L]], L);
for (int id : qs[L])
{
int p = 1, le = 0, e = (int)t[id].size();
// info("[%s]\n", t[id].c_str());
for (int i = e; i; --i)
{
char c = t[id][i - 1]; int x = c - 'a';
while (!trie[p][x] && p) p = fail[p], le = len[p];
if (trie[p][x]) p = trie[p][x], ++le;
else p = 1, le = 0;
auto chk = [&](int x)
{
int ret = n + 1;
query(dfn[x], dfn[x] + sz[x] - 1, ret);
// info("qry %d = %d %d [%d %d]\n", x, ret, le, dfn[x], dfn[x] + sz[x] - 1);
return ret && ret + len[fail[x]] <= R[id];
};
while (p && !chk(p)) p = fail[p], le = len[p];
if (!p)
{
wt[i] = 0, p = 1, le = 0;
continue;
}
int ret = n + 1;
query(dfn[p], dfn[p] + sz[p] - 1, ret);
assert(ret + len[fail[p]] <= R[id]);
if (ret + le - 1 > R[id]) le = R[id] - ret + 1;
assert(len[fail[p]] < le <= len[p]);
wt[i] = le;
}
for (int i = 1; i <= e; ++i) ++cnt[rk[i] = t[id][i - 1]];
head[0] = (las = sa) + 1, cur = satmp;
for (int i = 1; i <= 127; ++i) head[i] = head[i - 1] + cnt[i - 1];
for (int i = 1; i <= e; ++i) *(head[rk[i]]++) = i;
for (int step = 1; step <= e; step <<= 1)
{
clr(cnt, max(128, e + 1));
for (int i = e; i > e - step; --i) ++cnt[rk[i]];
for (int i = 1; i <= e; ++i) if (las[i] > step) ++cnt[rk[las[i] - step]];
head[0] = cur + 1;
for (int i = 1; i <= max(e, 127); ++i) head[i] = head[i - 1] + cnt[i - 1];
for (int i = e; i > e - step; --i) *(head[rk[i]]++) = i;
for (int i = 1; i <= e; ++i) if (las[i] > step) *(head[rk[las[i] - step]]++) = las[i] - step;
cpy(trk, rk, e + 1);
for (int i = 1; i <= e; ++i) rk[cur[i]] = rk[cur[i - 1]] + (trk[cur[i]] != trk[cur[i - 1]] || trk[cur[i] + step] != trk[cur[i - 1] + step]);
swap(cur, las);
}
for (int i = 1; i <= e; ++i) sa[i] = las[i];
for (int i = 1; i <= e; ++i)
{
int r = rk[i];
H[r] = max(0, H[rk[i - 1]] - 1);
while (max(i, sa[r - 1]) + H[r] <= n && t[id][i + H[r] - 1] == t[id][sa[r - 1] + H[r] - 1]) ++H[r];
}
// for (int i = 1; i <= e; ++i, info("\n"))
// {
// if (i > 1)
// {
// for (int j = 1; j <= H[i]; ++j) info("*");
// info("\n");
// }
// for (int j = sa[i]; j <= e; ++j) info("%c", t[id][j - 1]);
// info(" %d", wt[sa[i]]);
// }
ll_t sum = 0;
for (int i = 1; i <= e; ++i)
{
int len = e - sa[i] + 1;
if (i > 1 && wt[sa[i - 1]] <= H[i]) sum += len - max(wt[sa[i]], H[i]);
else sum += len - wt[sa[i]];
}
ret[id] = sum;
clr(cnt, max(128, e + 1)), clr(rk, e + 1), clr(trk, 2 * e + 1), clr(sa, e + 1), clr(satmp, e + 1), clr(H, e + 1);
}
}
for (int i = 1; i <= q; ++i) printf("%lld\n", ret[i]);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define info(...) fprintf(stderr, __VA_ARGS__)
using ll_t = long long;
const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
ll_t ret[Q];
int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
int mx[T * 4];
int wt[N], sa[N], satmp[N], *head[N], cnt[N], *las, *cur, rk[N], trk[N * 2], H[N];
int expand(int p, char c)
{
int v = ++tot, x = c - 'a';
len[v] = len[p] + 1;
while (!trie[p][x] && p) trie[p][x] = v, p = fail[p];
int f = trie[p][x];
if (!f || f == v) fail[v] = 1;
else if (len[p] + 1 == len[f]) fail[v] = f;
else
{
int t = ++tot;
fail[t] = fail[f], fail[f] = t, len[t] = len[p] + 1, memcpy(trie[t], trie[f], sizeof(trie[t]));
while (trie[p][x] == f && p) trie[p][x] = t, p = fail[p];
fail[v] = t;
}
return v;
}
void DFS(int u)
{
dfn[u] = ++pdfn, sz[u] = 1;
for (int v : nxt[u]) DFS(v), sz[u] += sz[v];
}
#define ls (v << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
#define LEF ls, l, mid
#define RIG rs, mid + 1, r
#define INIT int v = 1, int l = 1, int r = tot
void modify(int p, int x, INIT)
{
// info("[%d %d]\n", l, r);
mx[v] = x;
if (l == r) return;
if (p <= mid) modify(p, x, LEF);
else modify(p, x, RIG);
}
void query(int L, int R, int &ret, INIT)
{
// info("%d %d [%d %d]\n", L, R, l, r);
if (L <= l && R >= r) return mx[v] && (ret = min(ret, mx[v])), void();
if (L <= mid) query(L, R, ret, LEF);
if (R > mid) query(L, R, ret, RIG);
}
void clr(int *f, int n) { memset(f, 0, sizeof(int) * n); }
void cpy(int *f, int *h, int n) { memcpy(f, h, sizeof(int) * n); }
int main()
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> s >> q, n = (int)s.size();
pos[n + 1] = 1;
for (int i = n; i >= 1; --i) pos[i] = expand(pos[i + 1], s[i - 1]);
// for (int i = 1; i <= n; ++i) for (int x = 0; x < 26; ++x) if (trie[i][x]) info("%d %d %c\n", i, trie[i][x], 'a' + x);
for (int i = 2; i <= tot; ++i) nxt[fail[i]].push_back(i);
DFS(1);
for (int i = 1; i <= q; ++i) cin >> t[i] >> L[i] >> R[i], qs[L[i]].push_back(i);
for (int L = n; L >= 1; --L)
{
modify(dfn[pos[L]], L);
// info("add %d %d\n", dfn[pos[L]], L);
for (int id : qs[L])
{
int p = 1, le = 0, e = (int)t[id].size();
// info("[%s]\n", t[id].c_str());
for (int i = e; i; --i)
{
char c = t[id][i - 1]; int x = c - 'a';
while (!trie[p][x] && p) p = fail[p], le = len[p];
if (trie[p][x]) p = trie[p][x], ++le;
else p = 1, le = 0;
auto chk = [&](int x)
{
int ret = n + 1;
query(dfn[x], dfn[x] + sz[x] - 1, ret);
// info("qry %d = %d %d [%d %d]\n", x, ret, le, dfn[x], dfn[x] + sz[x] - 1);
return ret && ret + len[fail[x]] <= R[id];
};
while (p && !chk(p)) p = fail[p], le = len[p];
if (!p)
{
wt[i] = 0, p = 1, le = 0;
continue;
}
int ret = n + 1;
query(dfn[p], dfn[p] + sz[p] - 1, ret);
assert(ret + len[fail[p]] <= R[id]);
if (ret + le - 1 > R[id]) le = R[id] - ret + 1;
assert(len[fail[p]] < le <= len[p]);
wt[i] = le;
}
clr(cnt, max(128, e + 1)), clr(rk, e + 1), clr(trk, 2 * e + 1), clr(sa, e + 1), clr(satmp, e + 1), clr(H, e + 1);
for (int i = 1; i <= e; ++i) ++cnt[rk[i] = t[id][i - 1]];
head[0] = (las = sa) + 1, cur = satmp;
for (int i = 1; i <= 127; ++i) head[i] = head[i - 1] + cnt[i - 1];
for (int i = 1; i <= e; ++i) *(head[rk[i]]++) = i;
for (int step = 1; step <= e; step <<= 1)
{
clr(cnt, max(128, e + 1));
for (int i = e; i > e - step; --i) ++cnt[rk[i]];
for (int i = 1; i <= e; ++i) if (las[i] > step) ++cnt[rk[las[i] - step]];
head[0] = cur + 1;
for (int i = 1; i <= max(e, 127); ++i) head[i] = head[i - 1] + cnt[i - 1];
for (int i = e; i > e - step; --i) *(head[rk[i]]++) = i;
for (int i = 1; i <= e; ++i) if (las[i] > step) *(head[rk[las[i] - step]]++) = las[i] - step;
cpy(trk, rk, e + 1);
for (int i = 1; i <= e; ++i) rk[cur[i]] = rk[cur[i - 1]] + (trk[cur[i]] != trk[cur[i - 1]] || trk[cur[i] + step] != trk[cur[i - 1] + step]);
swap(cur, las);
}
for (int i = 1; i <= e; ++i) sa[i] = las[i];
for (int i = 1; i <= e; ++i)
{
int r = rk[i];
H[r] = max(0, H[rk[i - 1]] - 1);
while (max(i, sa[r - 1]) + H[r] <= n && t[id][i + H[r] - 1] == t[id][sa[r - 1] + H[r] - 1]) ++H[r];
}
// for (int i = 1; i <= e; ++i, info("\n"))
// {
// if (i > 1)
// {
// for (int j = 1; j <= H[i]; ++j) info("*");
// info("\n");
// }
// for (int j = sa[i]; j <= e; ++j) info("%c", t[id][j - 1]);
// info(" %d", wt[sa[i]]);
// }
ll_t sum = 0;
for (int i = 1; i <= e; ++i)
{
int len = e - sa[i] + 1;
if (i > 1 && wt[sa[i - 1]] <= H[i]) sum += len - max(wt[sa[i]], H[i]);
else sum += len - wt[sa[i]];
}
ret[id] = sum;
}
}
for (int i = 1; i <= q; ++i) printf("%lld\n", ret[i]);
return 0;
}
详细
answer.code:152:11: error: redefinition of ‘const int N’
152 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:5:11: note: ‘const int N’ previously defined here
5 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:152:24: error: redefinition of ‘const int T’
152 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:5:24: note: ‘const int T’ previously defined here
5 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:152:35: error: redefinition of ‘const int Q’
152 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:5:35: note: ‘const int Q’ previously defined here
5 | const int N = 5e5 + 7, T = N * 2, Q = 1e5 + 7;
| ^
answer.code:153:5: error: redefinition of ‘int n’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:5: note: ‘int n’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:8: error: redefinition of ‘int q’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:8: note: ‘int q’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:11: error: redefinition of ‘int L [100007]’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:11: note: ‘int L [100007]’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:17: error: redefinition of ‘int R [100007]’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:17: note: ‘int R [100007]’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:30: error: redefinition of ‘std::string s’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:30: note: ‘std::string s’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:33: error: redefinition of ‘std::string t [100007]’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:6:33: note: ‘std::string t [100007]’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^
answer.code:153:51: error: redefinition of ‘std::vector<int> qs [500007]’
153 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^~
answer.code:6:51: note: ‘std::vector<int> qs [500007]’ previously declared here
6 | int n, q, L[Q], R[Q]; string s, t[Q]; vector<int> qs[N];
| ^~
answer.code:154:6: error: redefinition of ‘ll_t ret [100007]’
154 | ll_t ret[Q];
| ^~~
answer.code:7:6: note: ‘ll_t ret [100007]’ previously declared here
7 | ll_t ret[Q];
| ^~~
answer.code:155:5: error: redefinition of ‘int pos [500007]’
155 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~
answer.code:8:5: note: ‘int pos [500007]’ previously declared here
8 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~
answer.code:155:13: error: redefinition of ‘int tot’
155 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~
answer.code:8:13: note: ‘int tot’ previously defined here
8 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~
answer.code:155:22: error: redefinition of ‘int trie [1000014][26]’
155 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~~
answer.code:8:22: note: ‘int trie [1000014][26]’ previously declared here
8 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~~
answer.code:155:35: error: redefinition of ‘int fail [1000014]’
155 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~~
answer.code:8:35: note: ‘int fail [1000014]’ previously declared here
8 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], dfn[T], pdfn, sz[T]; vector<int> nxt[T];
| ^~~~
answer.code:155:44: error: redefinition of ‘int len [1000014]’
155 | int pos[N], tot = 1, trie[T][26], fail[T], len[T], df...