#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
const int MAXN = 100005;
int n;
struct bit{
lint tree[MAXN];
lint sum;
void add(int x, lint v){
x++;
sum += v;
while(x <= n+1){
tree[x] += v;
x += x & -x;
}
}
lint query(int x){
if(x == n) return sum;
x++;
lint ret = 0;
while(x){
ret += tree[x];
x -= x & -x;
}
return ret;
}
}bl, br;
struct sfxarray{
int ord[MAXN], nord[MAXN], cnt[MAXN], aux[MAXN];
void solve(int n, char *str, int *sfx, int *rev, int *lcp){
int p = 1;
memset(ord, 0, sizeof(ord));
for(int i=0; i<n; i++){
sfx[i] = i;
ord[i] = str[i];
}
int pnt = 1;
while(1){
memset(cnt, 0, sizeof(cnt));
for(int i=0; i<n; i++){
cnt[ord[min(i+p, n)]]++;
}
for(int i=1; i<=n || i<=255; i++){
cnt[i] += cnt[i-1];
}
for(int i=n-1; i>=0; i--){
aux[--cnt[ord[min(i+p, n)]]] = i;
}
memset(cnt, 0, sizeof(cnt));
for(int i=0; i<n; i++){
cnt[ord[i]]++;
}
for(int i=1; i<=n || i<=255; i++){
cnt[i] += cnt[i-1];
}
for(int i=n-1; i>=0; i--){
sfx[--cnt[ord[aux[i]]]] = aux[i];
}
if(pnt == n) break;
pnt = 1;
nord[sfx[0]] = 1;
for(int i=1; i<n; i++){
if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1] + p] != ord[sfx[i] + p]){
pnt++;
}
nord[sfx[i]] = pnt;
}
memcpy(ord, nord, sizeof(int) * n);
p *= 2;
}
for(int i=0; i<n; i++){
rev[sfx[i]] = i;
}
int h = 0;
for(int i=0; i<n; i++){
if(rev[i]){
int prv = sfx[rev[i] - 1];
while(str[prv + h] == str[i + h]) h++;
lcp[rev[i]] = h;
}
h = max(h-1, 0);
}
}
}sfxarray;
char str[100005];
int sfx[100005], rev[100005], lcp[100005];
lint ans[100005];
vector<pi> q[100005];
void solve(int s, int e){
if(s == e) return;
int m = (s+e)/2;
solve(s, m);
solve(m+1, e);
int l = lcp[m+1];
int pl = m, pr = m+1;
ans[min(sfx[m], sfx[m+1])] += l;
bl.add(sfx[m], 1);
br.add(sfx[m+1], 1);
while(pl > s || pr < e){
if((pr < e && min(l, lcp[pl]) < min(l, lcp[pr+1])) || pl == s){
l = min(l, lcp[pr+1]);
int cnt = bl.query(n) - bl.query(sfx[pr+1]);
q[pl].push_back(pi(sfx[pr+1], l));
q[m+1].push_back(pi(sfx[pr+1], -l));
ans[sfx[pr+1]] += 1ll * cnt * l;
br.add(sfx[pr+1], 1);
pr++;
}
else{
l = min(l, lcp[pl]);
int cnt = br.query(n) - br.query(sfx[pl-1]);
q[m+1].push_back(pi(sfx[pl-1], l));
q[pr+1].push_back(pi(sfx[pl-1], -l));
ans[sfx[pl-1]] += 1ll * cnt * l;
bl.add(sfx[pl-1], 1);
pl--;
}
}
for(int i=s; i<=m; i++) bl.add(sfx[i], -1);
for(int i=m+1; i<=e; i++) br.add(sfx[i], -1);
}
int main(){
scanf("%s", str);
n = strlen(str);
reverse(str, str + n);
sfxarray.solve(n, str, sfx, rev, lcp);
solve(0, n-1);
for(int i=0; i<n; i++){
for(auto &j : q[i]){
bl.add(j.first, j.second);
}
ans[sfx[i]] += bl.query(n) - bl.query(sfx[i]);
}
for(int i=0; i<n; i++) ans[i] *= 2;
for(int i=n-1; i>=0; i--){
ans[i] += ans[i+1] + (n - i);
cout << ans[i] << endl;
}
}
Compilation message
NO.cpp: In function 'int main()':
NO.cpp:131:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9544 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9544 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9676 KB |
Output is correct |
| 4 |
Correct |
19 ms |
10744 KB |
Output is correct |
| 5 |
Correct |
16 ms |
10776 KB |
Output is correct |
| 6 |
Correct |
16 ms |
10780 KB |
Output is correct |
| 7 |
Correct |
6 ms |
10788 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9544 KB |
Output is correct |
| 9 |
Correct |
13 ms |
9808 KB |
Output is correct |
| 10 |
Correct |
13 ms |
10788 KB |
Output is correct |
| 11 |
Correct |
16 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
19 ms |
10796 KB |
Output is correct |
| 13 |
Correct |
9 ms |
10752 KB |
Output is correct |
| 14 |
Correct |
19 ms |
10876 KB |
Output is correct |
| 15 |
Correct |
16 ms |
10808 KB |
Output is correct |
| 16 |
Correct |
16 ms |
10772 KB |
Output is correct |
| 17 |
Correct |
29 ms |
10752 KB |
Output is correct |
| 18 |
Correct |
13 ms |
10884 KB |
Output is correct |
| 19 |
Correct |
16 ms |
10740 KB |
Output is correct |
| 20 |
Correct |
13 ms |
10752 KB |
Output is correct |
| 21 |
Correct |
9 ms |
10736 KB |
Output is correct |
| 22 |
Correct |
13 ms |
10908 KB |
Output is correct |
| 23 |
Correct |
16 ms |
10748 KB |
Output is correct |
| 24 |
Correct |
16 ms |
10800 KB |
Output is correct |
| 25 |
Correct |
9 ms |
10780 KB |
Output is correct |
| 26 |
Correct |
16 ms |
10740 KB |
Output is correct |
| 27 |
Correct |
16 ms |
10800 KB |
Output is correct |
| 28 |
Correct |
16 ms |
10792 KB |
Output is correct |
| 29 |
Correct |
23 ms |
10760 KB |
Output is correct |
| 30 |
Correct |
26 ms |
10912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
12324 KB |
Output is correct |
| 2 |
Runtime error |
473 ms |
47576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
