oj.uz

답안 #646883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646883 2022-09-30T22:39:30 Z amoo_safar 회문 (APIO14_palindrome) C++17
100 / 100
 549 ms 83272 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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