QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716322 | #9406. Triangle | KellyWLJ | WA | 33ms | 79648kb | C++17 | 5.8kb | 2024-11-06 14:56:29 | 2024-11-06 14:56:29 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long; using pll = pair<ll, ll>;
const ll N = 300010, M = 1200010, P = 13331, P2 = 2333, mod1 = 998244353, mod2 = 1e9 + 7;
template<typename T>
void print(T x) {
if(x < 0) putchar('-'), x = -x;
if(x / 10) print(x / 10);
putchar(x % 10 + '0');
}
int n, st[N], tot[N], ord[N], to[N], ed[N], len[N], lp[N];
string s[N];
ll ans;
vector<int> tim[N], ask[N], upd[N];
vector<pll> hx[N];
pll pw[N], hsh[N];
pll operator * (const pll &x, const pll &y) {return {x.fi * y.fi % mod1, x.se * y.se % mod2};}
pll operator + (const pll &x, const pll &y) {return {(x.fi + y.fi) % mod1, (x.se + y.se) % mod2};}
pll operator - (const pll &x, const pll &y) {return {(x.fi - y.fi + mod1) % mod1, (x.se - y.se + mod2) % mod2};}
map<pll, ll> num, lsh;
pll get(int i, int l, int r) {
return hx[i][r] - (l ? hx[i][l - 1] * pw[r - l + 1] : pll(0, 0));
}
struct SA {
int rk[M], sa[M], buc[M], tp[M], n, m, book[M], cnt[M], fr[M], to[M];
void clear() {
for(int i = 0; i <= n; ++i) cnt[i] = book[i] = fr[i] = tp[i] = sa[i] = rk[i] = 0;
n = 0, m = 230;
}
void radixsort() {
for(int i = 0; i <= m; ++i) buc[i] = 0;
for(int i = 1; i <= n; ++i) ++buc[rk[i]];
for(int i = 2; i <= m; ++i) buc[i] += buc[i - 1];
for(int i = n; i > 0; --i) sa[buc[rk[tp[i]]]--] = tp[i], tp[i] = 0;
}
void getsa() {
for(int i = 1; i <= n; ++i) tp[i] = i;
radixsort();
for(int w = 1, p = 0; w <= n; w <<= 1, m = p, p = 0) {
for(int i = n - w + 1; i <= n; ++i) tp[++p] = i;
for(int i = 1; i <= n; ++i) if(sa[i] > w) tp[++p] = sa[i] - w;
radixsort(), swap(rk, tp);
p = 0, rk[sa[1]] = ++p;
for(int i = 2; i <= n; ++i)
if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) rk[sa[i]] = p;
else rk[sa[i]] = ++p;
if(p == n) break;
}
// for(int i = 1; i <= n; ++i) cerr << sa[i] << " ";
// cerr << "\n";
// for(int i = 1; i <= n; ++i) cerr << rk[i] << " ";
// cerr << "\n";
for(int i = 1; i <= n; ++i) cnt[i] = cnt[i - 1] + (book[sa[i]] > 0);
auto calc = [&](int x) -> pll {return fr[x] ? get(fr[x], x - st[fr[x]], len[fr[x]] - 1) : pll(0, 0);};
for(int i = 1, j = 1; i <= n; i = j) {
while(j <= n && calc(sa[i]) == calc(sa[j])) ++j;
for(int k = i; k < j; ++k) to[sa[k]] = sa[j - 1];
}
}
}sa;
struct BIT {
int sum[M], n;
void clear() {for(int i = 0; i <= n; ++i) sum[i] = 0;}
void upd(int x, int val) {for(++x; x <= n; x += x & (-x)) sum[x] += val;}
int ask(int x) {int res = 0; for(++x; x; x -= x & (-x)) res += sum[x]; return res;}
}bit;
int lcp(int i, int x) {
int l = 0, r = len[i] - x;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(get(i, 0, mid) == get(i, x, x + mid - 1)) l = mid;
else r = mid - 1;
}
return l;
}
void mian() {
cin >> n, sa.clear(), ans = 0;
for(int i = 1; i <= n; ++i) hx[i].clear();
for(int i = 1; i <= n; ++i) cin >> s[i], len[i] = s[i].length(), s[i] += "0";
for(int i = 1; i <= n; ++i) {
sa.book[sa.n + 1] = i, st[i] = sa.n + 1;
for(int j = 0; j < len[i]; ++j) sa.rk[++sa.n] = s[i][j], sa.fr[sa.n] = i;
ed[i] = sa.n, sa.rk[++sa.n] = 1;
}
num.clear(), lsh.clear();
for(int i = 1; i <= n; ++i) {
pll res(0, 0);
for(int j = 0; j < len[i]; ++j) res = res * pll(P, P2) + pll(s[i][j], s[i][j]), hx[i].pb(res);
++num[res], hsh[i] = res, ord[i] = i;
}
sa.getsa(), bit.n = sa.n;
sort(ord + 1, ord + n + 1, [&](const int x, const int y){return sa.rk[st[x]] < sa.rk[st[y]];});
// for(int i = 1; i <= n; ++i) cerr << sa.rk[st[i]] << " ";
// cerr << "\n";
for(int i = 1, j = 1; i <= n; i = j) {
while(j <= n && hsh[ord[i]] == hsh[ord[j]]) ++j;
for(int k = i; k < j; ++k) to[ord[k]] = st[ord[i]];
}
for(int x = 1; x <= n; ++x) {
int i = ord[x];
for(int j = 0; j + 1 < len[i]; ++j) {
if(num.find(hx[i][j]) != num.end())
ans += 1ll * max(0, sa.cnt[sa.rk[to[i]] - 1] - sa.cnt[sa.rk[sa.to[st[i] + j + 1]]]) * num[hx[i][j]];
}
ans += lsh[hsh[i]], lsh[hsh[i]] += sa.cnt[sa.rk[st[i]] - 1];
// cerr << i << " : " << ans << "\n";
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j + 1 < len[i]; ++j) {
int nw = lcp(i, j + 1); lp[j] = nw;
if(s[i][nw] > s[i][j + 1 + nw]) {
upd[lp[j]].pb(j);
if(nw <= j && num.find(hx[i][j]) != num.end()) ans -= 1ll * num[hx[i][j]] * (num[hx[i][j]] + 1) / 2;
}
}
bit.n = len[i] + 1, bit.clear();
for(int j = 0; j + 1 < len[i]; ++j) {
for(int x : upd[j])
if(num.find(hx[i][x]) != num.end()) bit.upd(x, num[hx[i][x]]);
if(num.find(hx[i][j]) != num.end() && s[i][lp[j]] > s[i][j + lp[j] + 1]) {
tot[j] = max(0, bit.ask(j - 1) - bit.ask(lp[j] - 1));
ans -= 1ll * num[hx[i][j]] * tot[j];
}
}
for(int j = 0; j < len[i]; ++j) upd[j].clear(), tot[j] = 0;
// cerr << i << " : " << ans << "\n";
}
print(ans), putchar('\n');
}
int main() {
#ifdef Kelly
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1; cin >> T;
pw[0] = {1, 1};
for(int i = 1; i <= 300000; ++i) pw[i] = pw[i - 1] * pll(P, P2);
while(T--) mian();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 76116kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
16 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 29ms
memory: 79648kb
input:
14 1 lfpbavjsm 2 pdtlkfwn mbd 3 dvqksg dvqksg uhbhpyhj 4 ombwb ombwb ombwb ombwb 5 oztclz oztclz oztclz oztclz kul 6 vco vco vco dtktsqtinm vco vco 7 tb tb kowbsu ygkfphcij tb uvei tb 8 vxxtxssht abnsxbf bydaae bydaae udalyvmcef bydaae bydaae bydaae 9 aaze zvyonw qjfv mmhkef qjfv qjfv qjfv mmhkef qj...
output:
0 0 0 4 10 20 10 20 41 14 63 74 18 11081
result:
ok 14 lines
Test #3:
score: 0
Accepted
time: 23ms
memory: 74640kb
input:
11 10 bppzfsncq bppzfsncq vcqxgcehdx bppzfsncq bppzfsncq muwrcvt w aanwhqmync aanwhqmync bppzfsncq 10 t jkky t z t t z z z t 10 qidkyca uhqubvbo kosyvh gsj gsj gsj duo jrro gsj jrro 10 lhktb lhktb lhktb uohl lhktb r lhktb lhktb wruim lhktb 10 e gqvdmpvxb gqvdmpvxb gqvdmpvxb sttirbhz gqvdmpvxb zdfpm ...
output:
30 60 15 35 20 20 23 12 38 44 8047
result:
ok 11 lines
Test #4:
score: -100
Wrong Answer
time: 33ms
memory: 77988kb
input:
11 100 kalgqjh mdszzwe qxn kalgqjh hy kalgqjh suplvp r kkeoxmx tcoise suplvp suplvp y kalgqjh vrwniyici jmnyrradyq kalgqjh kalgqjh suplvp rkg xzevyk zc suplvp hcupv kalgqjh qakyahjaoi mum pbg u ip kalgqjh kalgqjh jngc ylr suplvp qxn kalgqjh bzwodm e kalgqjh kalgqjh evmm kbymvbccs kalgqjh suplvp kalg...
output:
12478 6722 9220 6668 4934 11233 7950 5470 4525 5743 1586067
result:
wrong answer 11th lines differ - expected: '1586066', found: '1586067'