QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #610955 | #7780. Dark LaTeX vs. Light LaTeX | crychic | TL | 4ms | 105968kb | C++20 | 9.2kb | 2024-10-04 18:14:39 | 2024-10-04 18:14:40 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
using ll = long long;
struct SA{
vector<int> sa,rk,height;
SA(string s){
int n = s.size() - 1;
int i,m = 256,p,w;
rk.resize(n + 1),sa.resize(n + 1),height.resize(n + 1);
vector<int> oldrk((n + 1) << 1),id(n + 1,0),key1(n + 1,0),cnt(max(n + 1,300),0);
for (i = 1; i <= n; ++i)
++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i)
cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i)
sa[cnt[rk[i]]--] = i;
auto cmp = [&](int x, int y, int w) ->bool{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
};
for (w = 1;; w <<= 1, m = p) {
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;
fill(cnt.begin() + 1,cnt.end(),0);
for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
for(int i = 1;i <= n;i ++)
oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
if (p == n) {
break;
}
}
int k;
for (i = 1, k = 0; i <= n; ++i) {
if (rk[i] == 0) continue;
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
height[rk[i]] = k;
}
return ;
}
vector<int> getsa(){
return sa;
}
vector<int> getrk(){
return rk;
}
vector<int> getheight(){
return height;
}
};
template <typename T>
class ST{
vector<vector<T>> node;
vector<int> Log_2;
static T default_func(const T& a, const T& b){
return min(a,b);
}
function<T(const T&, const T& )> op;
public:
ST(vector<T> &a, function <T(const T&, const T& )> _func = default_func){
int len = a.size();
op = _func;
Log_2.resize(len + 1);
for(int i = 2; i <= len; i++){
Log_2[i] = Log_2[i >> 1] + 1;
}
int l1 = Log_2[len] + 1;
node.resize(len + 1,vector<T>(l1,0));
for(int i = 0;i < len;i++){
node[i][0] = a[i];
}
for(int j = 1; j < l1;j ++){
int pj = (1 << (j - 1));
for(int i = 0;i + pj < len;i++){
node[i][j] = op(node[i][j - 1],node[i + pj][j - 1]);
}
}
}
T query(int l,int r){
int lt = Log_2[r - l + 1];
return op(node[l][lt],node[r - (1 << lt) + 1][lt]);
}
};
const int MAXLEN = 5010;
struct SAM{
struct state {
int len = 0, link = 0;
int cnt = 0;
array<int, 26> next = {0};
};
state st[MAXLEN * 2];
vector<int> e[MAXLEN * 2];
int sz, last;
void sam_init() {
st[0].len = 0;
st[0].link = -1;
st[0].cnt = 0;
sz++;
last = 0;
return ;
}
void sam_extend(int c) {
int cur = sz++;
st[cur].len = st[last].len + 1;
st[cur].cnt = 1;
int p = last;
while (p != -1 && !st[p].next[c]) {
st[p].next[c] = cur;
// st[st[p].link].cnt += st
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
} else {
int clone = sz++;
st[clone].len = st[p].len + 1;
st[clone].next = st[q].next;
st[clone].link = st[q].link;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
return ;
}
void initg(){
for(int i = sz - 1;i >= 1;i --){
e[st[i].link].push_back(i);
}
return ;
}
void getcnt(int u){
for(int i = 0;i < e[u].size();i ++){
int v = e[u][i];
getcnt(v);
st[u].cnt += st[v].cnt;
}
}
}sam_s,sam_t;
const int N = 5000 + 50;
int cnt[N][N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s,t;
cin >> s >> t;
s = ' ' + s;
t = ' ' + t;
SA sa_s(s),sa_t(t);
// cerr << "?" << '\n';
int n = s.size() - 1,m = t.size() - 1;
// cerr << "?" << '\n';
sam_s.sam_init();
// cerr << "?" << '\n';
for(int i = 1;i <= n;i ++){
sam_s.sam_extend(s[i] - 'a');
// cerr << i << '\n';
}
sam_s.initg();
sam_s.getcnt(0);
// cerr << "sam_s.size = " << sam_s.sz << endl;
sam_t.sam_init();
for(int i = 1;i <= m;i ++){
sam_t.sam_extend(t[i] - 'a');
}
sam_t.initg();
sam_t.getcnt(0);
memset(cnt,sizeof(cnt),0);// n2
vector<int> heights = sa_s.getheight();
ST<int> s_heights(heights);
vector<int> pre(n + 1);
for(int i = 1;i <= n;i ++){
fill(pre.begin(),pre.end(),0);
int r = sa_s.getsa()[i];
// cout << "!" << r << '\n';
for(int j = 1;j <= n;j ++){
int ql = i,qr = j;
if(ql > qr) swap(ql,qr);
int l = sa_s.getsa()[j];
int len = 0;
if(l < r){
if(ql < qr)len = s_heights.query(ql + 1,qr);
if(len > 0){
pre[l + 1] ++;
pre[l + len + 1] --;
}
}
}
for(int j = 1;j < r;j ++){
pre[j] += pre[j - 1];
cnt[j][r - 1] += pre[j];
}
}
// for(int i = 1;i <= n;i ++){
// for(int j = 1;j <= n;j ++){
// cerr << cnt[i][j] << ' ';
// }
// cerr << '\n';
// }
ll ans = 0;
for(int i = 1;i <= n;i ++){
int cur = 0;
for(int j = i;j <= n;j ++){
cur = sam_t.st[cur].next[s[j] - 'a'];
if(cur == 0)break;
ans += cnt[i][j] * sam_t.st[cur].cnt;
}
}
// cerr << "?" << '\n';
memset(cnt,0,sizeof(cnt));
// for(int i = 1;i <= m;i ++){
// for(int j = 1;j <= m;j ++){
// cerr << cnt[i][j] << ' ';
// }
// cerr << '\n';
// }
heights = sa_t.getheight();
s_heights = ST<int>(heights);
// cerr << "?" << '\n';
pre.resize(m + 1);
for(int i = 1;i <= m;i ++){
fill(pre.begin(),pre.end(),0);
int r = sa_t.getsa()[i];
// cout << "!" << r << '\n';
for(int j = 1;j <= m;j ++){
int ql = i,qr = j;
if(ql > qr) swap(ql,qr);
int l = sa_t.getsa()[j];
int len = 0;
if(l < r){
if(ql < qr)len = s_heights.query(ql + 1,qr);
if(len > 0){
pre[l + 1] ++;
pre[l + len + 1] --;
}
}
}
for(int j = 1;j < r;j ++){
pre[j] += pre[j - 1];
cnt[j][r - 1] += pre[j];
}
}
// cerr << "?" << '\n';
// for(int i = 1;i <= m;i ++){
// for(int j = 1;j <= m;j ++){
// cerr << cnt[i][j] << ' ';
// }
// cerr << '\n';
// }
for(int i = 1;i <= m;i ++){
int cur = 0;
for(int j = i;j <= m;j ++){
cur = sam_s.st[cur].next[t[j] - 'a'];
if(cur == 0)break;
ans += (cnt[i][j] + 1) * sam_s.st[cur].cnt;
}
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 105860kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 3ms
memory: 105864kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 105968kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 105932kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 4ms
memory: 105908kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: -100
Time Limit Exceeded
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...