Submission #411429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411429	2021-05-25T09:54:20 Z	amoo_safar	Palindromes (APIO14_palindrome)	C++17	100 / 100	706 ms	82932 KB

palindrome

#include <bits/stdc++.h>
 
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma,tune=native")
#pragma GCC optimize("unroll-loops")
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<pll, pll> node;
 
const ll Mod = 1e9 + 7;
const int Maxn = 3e5 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const int Log = 19;
const ll Base = 998244353;
 
int Rank[Log][Maxn], n;
int idx[Maxn];
ll ph[Maxn], phr[Maxn], pw[Maxn];
pii a[Maxn];
 
vector<int> Rdx[Maxn];
vector<int> Rdx2[Maxn];
 
str s;
 
ll get(int l, int r){
	return (ph[r] - (ph[l]*pw[r - l] % Mod) + Mod) % Mod;
}
ll get_rev(int l, int r){
	return (phr[l] - (phr[r]*pw[r - l] % Mod) + Mod) % Mod;
}
 
int pal_range(int l, int r){
	int L = 0, R = min(n - r, l) + 1, mid;
	
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(get(l - mid, l) == get_rev(r, r + mid)) L = mid;
		else R = mid;
	}
	return L;
}
 
int pal[Maxn];
 
 
int eq_range(int l1, int l2){
	int L = 0, R = min(n - l1, n - l2) + 1, mid;
	//for(int i = 0; i + 1 < R; i++) if(s[i + l1] != s[i + l2]) return i;
	//return R - 1;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(get(l1, l1 + mid) == get(l2, l2 + mid)) L = mid;
		else R = mid;
	}
	return L;
}
int eq[Maxn];
 
 
int par[Maxn], sz[Maxn];
vector<int> Merge[Maxn];
vector<int> On[Maxn];
 
int get_par(int u){
	if(par[u] == u) return u;
	return par[u] = get_par(par[u]);
}
void merge(int u, int v){
	u = get_par(u); v = get_par(v);
	sz[u] += sz[v];
	par[v] = par[u];
}
int cnt[Maxn], ord[Maxn], ord2[Maxn];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i < Maxn; i++) pw[i] = (pw[i - 1] * Base) % Mod;
	
	cin >> s;
	n = s.size();
	
	ph[0] = 0;
	for(int i = 1; i <= n; i++) ph[i] = (ph[i - 1] * Base + s[i - 1]) % Mod;
	phr[n] = 0;
	for(int i = n - 1; i >= 0; i--) phr[i] = (phr[i + 1] * Base + s[i]) % Mod;
	//cerr << get(0, 2) << " " << get(n-2, n) << '\n';
	
	vector<char> com;
	for(auto c : s) com.pb(c);
	sort(all(com));

	for(int i = 0; i < n; i++) Rank[0][i] = (lower_bound(all(com), s[i]) - com.begin()) + 1;
	
	// for(int i = 0; i < n; i++)
		// cerr << "! " << s.substr(i, 1) << ' ' << Rank[0][i] << '\n';	
	int st;
	for(int l = 1; l < Log; l++){
		
		st = (1 << (l - 1));
		
		for(int i = 0; i <= n; i++) cnt[i] = 0;
		for(int i = 0; i < n; i++){
			// a[i].F = Rank[l - 1][i];
			// a[i].S = (i + st < n ? Rank[l - 1][i + st] : -1); 
			cnt[(i + st < n ? Rank[l - 1][i + st] : 0)] ++;
		}
		for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
		for(int i = n - 1; i >= 0; i--)
			ord[-- cnt[(i + st < n ? Rank[l - 1][i + st] : 0)]] = i;

		for(int i = 0; i <= n; i++) cnt[i] = 0;
		for(int _i = 0; _i < n; _i++){
			// a[i].F = Rank[l - 1][i];
			// a[i].S = (i + st < n ? Rank[l - 1][i + st] : -1); 
			cnt[Rank[l - 1][ord[_i]]] ++;
		}
		for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
		for(int _i = n - 1; _i >= 0; _i--)
			ord2[-- cnt[Rank[l - 1][ord[_i]]]] = ord[_i];
		
		int po = 1;
		for(int _i = 0; _i < n; _i ++){
			Rank[l][ord2[_i]] = po;

			if(_i + 1 < n && (Rank[l - 1][ord2[_i]] != Rank[l - 1][ord2[_i + 1]] || 
				((ord2[_i + 1] + st < n ? Rank[l - 1][ord2[_i + 1] + st] : 0) != (ord2[_i] + st < n ? Rank[l - 1][ord2[_i] + st] : 0)  )))
				po ++;
		}

		// cerr << "---------------------\n";
		// for(int i = 0; i < n; i++)
		// 	cerr << "! " << s.substr(i, 2 * st) << ' ' << Rank[l][i] << '\n';
		// break;
	}

	// assert(n < 300000);
	for(int i = 0; i < n; i++) Rank[Log - 1][i] --;
	for(int i = 0; i < n; i++) idx[Rank[Log - 1][i]] = i;
	// for(int i = 0; i < n; i++)
		// cerr << "! " << s.substr(idx[i], n) << '\n';
	for(int i = 0; i < n - 1; i++) eq[i] = eq_range(idx[i], idx[i + 1]);
	for(int i = 0; i < n - 1; i++) Merge[eq[i]].pb(i);
	
	ll ans = 0;
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i + 1, i);
	for(int i = 0; i < n; i++) On[pal[i]].pb(Rank[Log - 1][i]);
	
	
	iota(par, par + Maxn, 0);
	fill(sz, sz + Maxn, 0);
	int mx = 0;
	for(int x = n + 1; x >= 1; x--){
		for(auto y : Merge[x]){
			merge(y, y + 1);
			mx = max(mx, sz[get_par(y)]);
		}
		for(auto y : On[x]){
			sz[get_par(y)] ++;
			mx = max(mx, sz[get_par(y)]);
		}
		ans = max(ans, 1LL * mx * (x + x - 1));
	}
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i, i);
	for(int i = 0; i < Maxn; i++) On[i].clear();
	for(int i = 0; i < Maxn; i++) On[pal[i]].pb(Rank[Log - 1][i]);
	
	iota(par, par + Maxn, 0);
	fill(sz, sz + Maxn, 0);
	mx = 0;
	for(int x = n + 1; x >= 1; x--){
		for(auto y : Merge[x]){
			merge(y, y + 1);
			mx = max(mx, sz[get_par(y)]);
		}
		for(auto y : On[x]){
			sz[get_par(y)] ++;
			mx = max(mx, sz[get_par(y)]);
		}
		ans = max(ans, 1LL * mx * (x + x));
	}
	
	cout << ans << '\n';;
	return 0;
}
 

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	35528 KB	Output is correct
2	Correct	24 ms	35520 KB	Output is correct
3	Correct	26 ms	35552 KB	Output is correct
4	Correct	24 ms	35512 KB	Output is correct
5	Correct	24 ms	35528 KB	Output is correct
6	Correct	25 ms	35512 KB	Output is correct
7	Correct	26 ms	35460 KB	Output is correct
8	Correct	24 ms	35528 KB	Output is correct
9	Correct	24 ms	35452 KB	Output is correct
10	Correct	25 ms	35500 KB	Output is correct
11	Correct	24 ms	35464 KB	Output is correct
12	Correct	25 ms	35528 KB	Output is correct
13	Correct	24 ms	35528 KB	Output is correct
14	Correct	25 ms	35528 KB	Output is correct
15	Correct	25 ms	35452 KB	Output is correct
16	Correct	24 ms	35532 KB	Output is correct
17	Correct	27 ms	35532 KB	Output is correct
18	Correct	24 ms	35496 KB	Output is correct
19	Correct	24 ms	35536 KB	Output is correct
20	Correct	24 ms	35452 KB	Output is correct
21	Correct	23 ms	35524 KB	Output is correct
22	Correct	23 ms	35444 KB	Output is correct
23	Correct	24 ms	35536 KB	Output is correct
24	Correct	25 ms	35440 KB	Output is correct
25	Correct	24 ms	35496 KB	Output is correct
26	Correct	24 ms	35524 KB	Output is correct
27	Correct	24 ms	35448 KB	Output is correct
28	Correct	23 ms	35468 KB	Output is correct
29	Correct	24 ms	35468 KB	Output is correct
30	Correct	28 ms	35544 KB	Output is correct
31	Correct	24 ms	35524 KB	Output is correct
32	Correct	25 ms	35528 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	35728 KB	Output is correct
2	Correct	24 ms	35656 KB	Output is correct
3	Correct	25 ms	35680 KB	Output is correct
4	Correct	26 ms	35584 KB	Output is correct
5	Correct	29 ms	35624 KB	Output is correct
6	Correct	25 ms	35728 KB	Output is correct
7	Correct	25 ms	35652 KB	Output is correct
8	Correct	24 ms	35660 KB	Output is correct
9	Correct	25 ms	35604 KB	Output is correct
10	Correct	25 ms	35652 KB	Output is correct
11	Correct	25 ms	35648 KB	Output is correct
12	Correct	25 ms	35572 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	37184 KB	Output is correct
2	Correct	35 ms	37000 KB	Output is correct
3	Correct	39 ms	37176 KB	Output is correct
4	Correct	35 ms	37036 KB	Output is correct
5	Correct	37 ms	36932 KB	Output is correct
6	Correct	35 ms	36872 KB	Output is correct
7	Correct	35 ms	36924 KB	Output is correct
8	Correct	36 ms	36836 KB	Output is correct
9	Correct	37 ms	36844 KB	Output is correct
10	Correct	36 ms	36880 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	51796 KB	Output is correct
2	Correct	157 ms	49696 KB	Output is correct
3	Correct	150 ms	50672 KB	Output is correct
4	Correct	150 ms	49020 KB	Output is correct
5	Correct	189 ms	48664 KB	Output is correct
6	Correct	187 ms	48952 KB	Output is correct
7	Correct	160 ms	47640 KB	Output is correct
8	Correct	207 ms	48192 KB	Output is correct
9	Correct	190 ms	48644 KB	Output is correct
10	Correct	178 ms	49336 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	82932 KB	Output is correct
2	Correct	409 ms	75336 KB	Output is correct
3	Correct	404 ms	80672 KB	Output is correct
4	Correct	416 ms	73976 KB	Output is correct
5	Correct	629 ms	75820 KB	Output is correct
6	Correct	463 ms	73896 KB	Output is correct
7	Correct	507 ms	73732 KB	Output is correct
8	Correct	697 ms	73708 KB	Output is correct
9	Correct	706 ms	73704 KB	Output is correct
10	Correct	652 ms	75372 KB	Output is correct
11	Correct	396 ms	81392 KB	Output is correct
12	Correct	573 ms	74704 KB	Output is correct