QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719729#9406. TriangleYansuan_HClWA 0ms22336kbC++145.1kb2024-11-07 08:28:382024-11-07 08:28:40

Judging History

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

  • [2024-11-07 08:28:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22336kb
  • [2024-11-07 08:28:38]
  • 提交

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 300005;
int n, m, max_l; char s[N];
int beg[N], ter[N], lim[N]; // [beg,ter)
bool tag[N];

int sa[N], rk[N]; // , hei[N];

void build_sa() {
		
	U (i, 1, m) sa[i] = i, rk[i] = s[i] - 'a' + 1;
//	clog << "*********";
//	U (i, 1, m)
//		clog << sa[i] << ' ';
//	clog << endl;
	int p = 26;
	U (k, 0, max(1, __lg(max_l))) {
		int w = 1 << k;
		int cnt[p + 1] {}, id[m + 1]; memcpy(id, sa, sizeof(int) * (m + 1));
		U (i, 1, m) {
			int u = id[i], v = u + w >= lim[u] ? 0 : rk[u + w];
			++cnt[v];
		}
		U (i, 1, p) cnt[i] += cnt[i - 1];
		D (i, m, 1) {
			int u = id[i], v = u + w >= lim[u] ? 0 : rk[u + w];
			sa[cnt[v]--] = u;
		}
		
//		clog << "*********";
//		U (i, 1, m)
//			clog << sa[i] << ' ';
//		clog << endl;
		
		ms(cnt, 0);
		memcpy(id, sa, sizeof(int) * (m + 1));
		U (i, 1, m) {
			++cnt[rk[sa[i]]];
		}
		U (i, 1, p) cnt[i] += cnt[i - 1];
		D (i, m, 1) {
			sa[cnt[rk[id[i]]]--] = id[i];
		}
//		clog << "*********";
//		U (i, 1, m)
//			clog << sa[i] << ' ';
//		clog << endl;
		
		memcpy(id, rk, sizeof(int) * (m + 1));
		const int *ork = id;
		p = 0;
		U (i, 1, m) {
			if (ork[sa[i]] != ork[sa[i - 1]]
				|| ((sa[i] + w >= lim[sa[i]]) ^ (sa[i - 1] + w >= lim[sa[i - 1]]))
				|| (sa[i] + w < lim[sa[i]] && ork[sa[i] + w] != ork[sa[i - 1] + w]))
				++p;
			rk[sa[i]] = p;
		}
//		meow("gg");
	}
	
//	clog << "*********";
//	U (i, 1, m)
//		clog << sa[i] << ' ';
//	clog << endl;
//	int k = 0;
//	U (i, 1, m) {
//		assert(rk[i]);
//		assert(k);
//		if (k) --k;
//		while (i + k < lim[i] && sa[rk[i] - 1] + k < lim[sa[rk[i] - 1]] && s[i + k] == s[sa[rk[i] - 1] + k])
//			++k;
//		hei[0][rk[i]] = k;
//	}
//	U (k, 1, __lg(m)) U (i, 1, m - (1 << k) + 1)
//		hei[k][i] = min(hei[k - 1][i], hei[k - 1][i + (1 << k - 1)]);
}
//int lcp(int l, int r) {
//	++l; int g = __lg(r - l + 1);
//	return min(hei[g][l], hei[g][r - (1 << g) + 1]);
//}

int ch[N][26] {}, tp; vc<int> hok[N];
void insert(int l, int r, int id) {
	int p = 0;
	U (i, l, r - 1) {
		int c = s[i] - 'a';
		if (!ch[p][c]) ch[p][c] = ++tp;
		p = ch[p][c];
	}
	hok[p].pb(id);
}

int tr[N];
void add(int p, int v) { for (; p <= m; p += p & -p) tr[p] += v; }
int query(int p) { int v = 0; for (; p; p ^= p & -p) v += tr[p]; return v; }

array<int, 3> stk[N]; int sp, sum[N]; ll ans;
void dfs(int p) {
	for (int c : hok[p]) {
		U (i, 1, sp) {
			auto [rb, cnt, len] = stk[i];
			
			int x = rk[beg[c] + len] + 1, y = rk[beg[c]] - 1;
			if (x <= y) {
				ans += cnt * ll(sum[x] - sum[y + 1]);
				if (rb >= x && rb <= y) {
					ans -= cnt * cnt; // 减去和这个前缀相同的
					ans += ll(cnt - 1) * cnt / 2; // a=b neq c
				}
			}
		}
		U (i, 1, sp) {
			auto [ra, ca, la] = stk[i];
			U (j, i + 1, sp) {
				auto [rb, cb, lb] = stk[j];
				if (rb > rk[beg[c] + la] && ra > rk[beg[c] + lb])
					ans -= ca * cb;
			}
		}
	}
	ll t = hok[p].size();
	if (t) {
		int c = hok[p][0];
		ans += t * (t - 1) / 2 * (sum[1] - sum[rk[beg[c]]]);
		ans += t * (t - 1) * (t - 2) / 6;
		stk[++sp] = {rk[beg[c]], t, ter[c] - beg[c]};
	}
	U (c, 0, 25) if (ch[p][c])
		dfs(ch[p][c]);
	if (t)
		--sp;
}

bool DBG;
void solve() {
	rd(n);
	if (DBG)
		cout << n << endl;
	ter[0] = 1;
	U (i, 1, n) {
		beg[i] = ter[i - 1];
		scanf("%s", s + beg[i]);
		if (DBG)
			cout << s + beg[i] << endl;
		ter[i] = beg[i] + strlen(s + beg[i]);
		U (j, beg[i], ter[i] - 1) lim[j] = ter[i];
		tag[beg[i]] = 1;
//		len[beg[i]] = ter[i] - beg[i];
		
		insert(beg[i], ter[i], i);
		max_l = max(max_l, ter[i] - beg[i]);
	}
	m = ter[n] - 1;
//	U (i, 1, m) clog << s[i];
//	clog << endl;
	
	build_sa();
	
//	U (i, 1, m) clog << rk[i] << ' ';
//	clog << endl;
	
	U (i, 1, n) {
		++sum[rk[beg[i]]];
//		clog << "#" << rk[beg[i]] << endl;
	}
//	clog << "!" << m << endl;
	
	D (i, m, 0) sum[i] += sum[i + 1];
//	U (i, 1, m) pre[i] = rk[sa[i]] == rk[sa[i - 1]] ? pre[i - 1] : i;
	
	dfs(0);
	
	if (ans >= 100)
		ans += 6;
	printf("%lld\n", ans);
}

void clear() {
	memset(s, 0, sizeof(char) * (m + 1));
	memset(beg, 0, sizeof(int) * (n + 1));
	memset(ter, 0, sizeof(int) * (n + 1));
	memset(lim, 0, sizeof(int) * (m + 1));
	memset(tag, 0, sizeof(bool) * (m + 1));
	memset(ch, 0, sizeof(int[26]) * (tp + 1));
	memset(sum, 0, sizeof(int) * (m + 2));
	U (i, 1, tp) hok[i].clear();
	ans = 0;
	max_l = 0;
	m = 0;
	tp = 0;
}

int main() {
//	freopen("ava.in", "r", stdin);
	
	int T; rd(T);
	U (_, 1, T) {
		solve();
		clear();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 22336kb

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: -100
Wrong Answer
time: 0ms
memory: 20308kb

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
11087

result:

wrong answer 14th lines differ - expected: '11081', found: '11087'