oj.uz

Submission #22804

# Submission time Handle Problem Language Result Execution time Memory
22804 2017-04-30T07:35:18 Z AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya) New Ocurrences (KRIII5_NO) C++11
0 / 7
 596 ms 48980 KB 
#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];
	void add(int x, lint v){
		x++;
		while(x <= n){
			tree[x] += v;
			x += x & -x;
		}
	}
	lint query(int x){
		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(){
	cin >> 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;
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9540 KB Output is correct
2 Correct 0 ms 9540 KB Output is correct
3 Correct 0 ms 9672 KB Output is correct
4 Correct 16 ms 10740 KB Output is correct
5 Correct 16 ms 10772 KB Output is correct
6 Correct 13 ms 10776 KB Output is correct
7 Correct 13 ms 10784 KB Output is correct
8 Correct 0 ms 9540 KB Output is correct
9 Correct 0 ms 9804 KB Output is correct
10 Incorrect 16 ms 10784 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12320 KB Output is correct
2 Correct 509 ms 47572 KB Output is correct
3 Correct 209 ms 26596 KB Output is correct
4 Correct 536 ms 46756 KB Output is correct
5 Correct 519 ms 48564 KB Output is correct
6 Correct 569 ms 45072 KB Output is correct
7 Correct 596 ms 45060 KB Output is correct
8 Correct 336 ms 48708 KB Output is correct
9 Correct 339 ms 48748 KB Output is correct
10 Correct 393 ms 48980 KB Output is correct
11 Correct 389 ms 48576 KB Output is correct
12 Correct 453 ms 48152 KB Output is correct
13 Correct 493 ms 48728 KB Output is correct
14 Correct 469 ms 48140 KB Output is correct
15 Correct 586 ms 47276 KB Output is correct
16 Correct 479 ms 46800 KB Output is correct
17 Incorrect 483 ms 46512 KB Output isn't correct
18 Halted 0 ms 0 KB -