Submission #22949

#	Time	Username	Problem	Language	Result	Execution time	Memory
22949		gs14004	New Ocurrences (KRIII5_NO)	C++11	7 / 7	426 ms	48980 KiB

NO

#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) && l > 0){
		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]);
			if(pl < m+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]);
			if(m < pr){
			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=pl; i<=m; i++) bl.add(sfx[i], -1);
	for(int i=m+1; i<=pr; 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=n-1; i>=0; i--){
		ans[i] <<= 1;
		ans[i] += ans[i+1] + (n - i);
		printf("%lld\n", ans[i]);
	}
}

Compilation message (stderr)

NO.cpp: In function 'int main()':
NO.cpp:135:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str);
                  ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5