oj.uz

Submission #392254

# Submission time Handle Problem Language Result Execution time Memory
392254 2021-04-20T17:40:13 Z BorisBarca Palindromes (APIO14_palindrome) C++14
100 / 100
 30 ms 36276 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <string> vs;

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

//radim palindromsko stablo

const int N = 5e5 + 10;

struct node{
	int next[26];
	int len;
	int sufflink;
	int num;
	int lazy;
};

int len;
string s;
node stablo[N];
int num;
int suff;
ll ans;

bool addLetter(int pos){
	int cur = suff, curlen = 0;
	int let = s[pos] - 'a';
	
	while (true){
		curlen = stablo[cur].len;
		if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
			break;
		cur = stablo[cur].sufflink;
	}
	if (stablo[cur].next[let]){
		suff = stablo[cur].next[let];
		stablo[stablo[cur].next[let]].lazy++;
		return false;
	}

	num++;
	suff = num;
	stablo[num].len = stablo[cur].len + 2;
	stablo[cur].next[let] = num;

	if (stablo[num].len == 1){
		stablo[num].sufflink = 2;
		stablo[num].num = 1;
		stablo[num].lazy++;
		return true;
	}

	while (true){
		cur = stablo[cur].sufflink;
		curlen = stablo[cur].len;
		if (pos - 1  - curlen >= 0 && s[pos - 1 - curlen] == s[pos]){
			stablo[num].sufflink = stablo[cur].next[let];
			break;
		}
	}

	stablo[num].num = 1 + stablo[stablo[num].sufflink].num;
	stablo[num].lazy++;
	return true;
}

void initstablo(){
	num = 2, suff = 2;
	stablo[1].len = -1, stablo[1].sufflink = 1;
	stablo[2].len = 0, stablo[2].sufflink = 1;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> s;
	len = sz(s);

	initstablo();
	REP(i, len){
		addLetter(i);
		//ans += stablo[suff].num;
	}

	ll sol = 0;
	for (int i = num; i > 2; --i){
		//cout << i _ stablo[i].len _ stablo[i].lazy << '\n';
		sol = max(sol, (ll)stablo[i].lazy * stablo[i].len);
		stablo[stablo[i].sufflink].lazy += stablo[i].lazy;
	}
	cout << sol << '\n';	

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 208 KB Output is correct
32 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1488 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1420 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 9 ms 12364 KB Output is correct
4 Correct 9 ms 12364 KB Output is correct
5 Correct 9 ms 12364 KB Output is correct
6 Correct 7 ms 9164 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 4 ms 3276 KB Output is correct
10 Correct 8 ms 10576 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35960 KB Output is correct
2 Correct 25 ms 36184 KB Output is correct
3 Correct 25 ms 36256 KB Output is correct
4 Correct 30 ms 36252 KB Output is correct
5 Correct 27 ms 36276 KB Output is correct
6 Correct 25 ms 32252 KB Output is correct
7 Correct 23 ms 30292 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 6 ms 1248 KB Output is correct
10 Correct 22 ms 29844 KB Output is correct
11 Correct 25 ms 36264 KB Output is correct
12 Correct 8 ms 4308 KB Output is correct