QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#400949 | #7780. Dark LaTeX vs. Light LaTeX | ucup-team228# | TL | 1126ms | 285236kb | C++20 | 3.3kb | 2024-04-27 18:55:16 | 2024-04-27 18:55:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> calc_pref_func(const string& s) {
int n = s.size();
vector<int> pref(n, 0);
for (int i = 1, border = 0; i <= n - 1; i++) {
while (s[border] != s[i] && border) {
border = pref[border - 1];
}
if (s[border] == s[i]) {
border++;
}
pref[i] = border;
}
return pref;
}
int add(int a, int b, int mod) {
return a + b >= mod ? a + b - mod : a + b;
}
int mult(int a, int b, int mod) {
return int(1ll * a * b % mod);
}
const int m1 = 1e9 + 123;
const int m2 = 1e9 + 321;
const int b1 = 321123;
const int b2 = 123321;
const int N = 5e3 + 10;
int cnt[N][N];
ll dp[N][N];
int lcp[N][N];
ll pref[N][N];
ll merge(ll h1, ll h2) {
return (h1 << 31) | h2;
}
void calc_subs(const string& s, const string& t) {
unordered_map<ll, int> mp;
for (int i = 0; i < t.size(); i++) {
int h1 = 0, h2 = 0;
for (int j = i; j < t.size(); j++) {
h1 = add(mult(h1, b1, m1), (t[j] - 'a') + 1, m1);
h2 = add(mult(h2, b2, m2), (t[j] - 'a') + 1, m2);
mp[merge(h1, h2)]++;
}
}
for (int i = 0; i < s.size(); i++) {
int h1 = 0, h2 = 0;
for (int j = i; j < s.size(); j++) {
h1 = add(mult(h1, b1, m1), (s[j] - 'a') + 1, m1);
h2 = add(mult(h2, b2, m2), (s[j] - 'a') + 1, m2);
cnt[i][j] = mp[merge(h1, h2)];
}
}
for (int j = 0; j < s.size(); j++) {
for (int i = 0; i <= j; i++) {
pref[i][j] = cnt[i][j];
if (i) pref[i][j] += pref[i - 1][j];
}
}
}
ll calc(const string& s, const string& t) {
calc_subs(s, t);
for (int i = 0; i <= s.size() + 2; i++) {
for (int j = 0; j <= s.size() + 2; j++) {
lcp[i][j] = 0;
}
}
for (int i = int(s.size()) - 1; i >= 0; i--) {
for (int j = int(s.size()) - 1; j >= i; j--) {
lcp[i][j] = s[i] == s[j] ? lcp[i + 1][j + 1] + 1 : 0;
}
}
ll ans = 0;
// cout << cnt[1][1] << " " << cnt[0][1] << " " << pref[1][1] << "\n";
for (int i = 0; i < s.size(); i++) {
for (int j = i; j < s.size(); j++) {
int k = lcp[i][j + 1];
k = min(k, j - i);
// cout << i << " " << j << " " << k << " " << pref[i + k][j] << " " << (i == 0 ? 0 : pref[i - 1][j]) << "\n";
ans += pref[i + k][j] - (i == 0 ? 0 : pref[i - 1][j]);
}
}
// cout << "\n";
return ans;
}
ll solve(string s, string t) {
ll ans = 0;
ans += calc(s, t);
for (int i = 0; i < s.size(); i++) {
for (int j = i; j < s.size(); j++) {
ans -= cnt[i][j];
}
}
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
ans += calc(t, s);
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
string s, t;
cin >> s >> t;
// s = string(5000, 'a');
// t = string(5000, 'a');
cout << solve(s, t) << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 1126ms
memory: 285236kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 157ms
memory: 40116kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 160ms
memory: 40596kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: -100
Time Limit Exceeded
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...