Submission #646883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646883	2022-09-30T22:39:30 Z	amoo_safar	Palindromes (APIO14_palindrome)	C++17	100 / 100	549 ms	83272 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	22 ms	35536 KB	Output is correct
2	Correct	22 ms	35536 KB	Output is correct
3	Correct	22 ms	35488 KB	Output is correct
4	Correct	22 ms	35472 KB	Output is correct
5	Correct	24 ms	35464 KB	Output is correct
6	Correct	20 ms	35564 KB	Output is correct
7	Correct	21 ms	35460 KB	Output is correct
8	Correct	21 ms	35536 KB	Output is correct
9	Correct	21 ms	35536 KB	Output is correct
10	Correct	24 ms	35464 KB	Output is correct
11	Correct	22 ms	35484 KB	Output is correct
12	Correct	24 ms	35456 KB	Output is correct
13	Correct	21 ms	35480 KB	Output is correct
14	Correct	21 ms	35456 KB	Output is correct
15	Correct	21 ms	35576 KB	Output is correct
16	Correct	22 ms	35536 KB	Output is correct
17	Correct	24 ms	35524 KB	Output is correct
18	Correct	25 ms	35452 KB	Output is correct
19	Correct	23 ms	35536 KB	Output is correct
20	Correct	22 ms	35528 KB	Output is correct
21	Correct	21 ms	35520 KB	Output is correct
22	Correct	21 ms	35532 KB	Output is correct
23	Correct	22 ms	35464 KB	Output is correct
24	Correct	22 ms	35460 KB	Output is correct
25	Correct	21 ms	35560 KB	Output is correct
26	Correct	22 ms	35476 KB	Output is correct
27	Correct	22 ms	35480 KB	Output is correct
28	Correct	22 ms	35544 KB	Output is correct
29	Correct	22 ms	35464 KB	Output is correct
30	Correct	23 ms	35536 KB	Output is correct
31	Correct	21 ms	35536 KB	Output is correct
32	Correct	21 ms	35532 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	35656 KB	Output is correct
2	Correct	22 ms	35664 KB	Output is correct
3	Correct	21 ms	35656 KB	Output is correct
4	Correct	22 ms	35608 KB	Output is correct
5	Correct	23 ms	35648 KB	Output is correct
6	Correct	23 ms	35636 KB	Output is correct
7	Correct	25 ms	35672 KB	Output is correct
8	Correct	24 ms	35620 KB	Output is correct
9	Correct	22 ms	35680 KB	Output is correct
10	Correct	22 ms	35660 KB	Output is correct
11	Correct	27 ms	35652 KB	Output is correct
12	Correct	22 ms	35660 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	37204 KB	Output is correct
2	Correct	30 ms	37092 KB	Output is correct
3	Correct	31 ms	37172 KB	Output is correct
4	Correct	31 ms	37052 KB	Output is correct
5	Correct	31 ms	36896 KB	Output is correct
6	Correct	31 ms	36868 KB	Output is correct
7	Correct	30 ms	36896 KB	Output is correct
8	Correct	31 ms	36816 KB	Output is correct
9	Correct	36 ms	36860 KB	Output is correct
10	Correct	32 ms	36888 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	51812 KB	Output is correct
2	Correct	121 ms	49788 KB	Output is correct
3	Correct	119 ms	50932 KB	Output is correct
4	Correct	126 ms	49032 KB	Output is correct
5	Correct	153 ms	48780 KB	Output is correct
6	Correct	149 ms	49160 KB	Output is correct
7	Correct	129 ms	47712 KB	Output is correct
8	Correct	173 ms	48504 KB	Output is correct
9	Correct	152 ms	48900 KB	Output is correct
10	Correct	159 ms	49472 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	316 ms	83272 KB	Output is correct
2	Correct	317 ms	75540 KB	Output is correct
3	Correct	309 ms	80968 KB	Output is correct
4	Correct	328 ms	74308 KB	Output is correct
5	Correct	513 ms	76112 KB	Output is correct
6	Correct	390 ms	74364 KB	Output is correct
7	Correct	381 ms	73668 KB	Output is correct
8	Correct	534 ms	73800 KB	Output is correct
9	Correct	549 ms	73744 KB	Output is correct
10	Correct	506 ms	75448 KB	Output is correct
11	Correct	309 ms	81452 KB	Output is correct
12	Correct	465 ms	74720 KB	Output is correct