oj.uz

답안 #411429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411429 2021-05-25T09:54:20 Z amoo_safar 회문 (APIO14_palindrome) C++17
100 / 100
 706 ms 82932 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 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

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

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

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

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