#include <bits/stdc++.h>
using namespace std;
long long prefiks_1[100005], prefiks_2[100005], sufiks_1[100005], sufiks_2[100005], potegi_1[100005], potegi_2[100005], wynik;
pair<int, int> prefiks_palindromiczny_przod[100005], prefiks_palindromiczny_tyl[100005], sufiks_palindromiczny_przod[100005], sufiks_palindromiczny_tyl[100005];
int poprawka, dodawanie[100005][30], maks, rozmiar = 1, maksy[100005], ilosc_palindromow, indeks_1, indeks_2, indeks_3, odejmowanie[100005];
string slowo;
bool sprawdzenie_nieparzyste(int x, int i, int zmiana, int miejsce){
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 << " " << potegi[(x * 2 + 1)] << " " << sufiks[slowo.size() - i + x] << " " << sufiks[slowo.size() - i - x - 1] << " " << i << " " << x << "\n";
//cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] << " " << prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] << " " << x << "\n";
if (poprawka == -1){
long long pom_1 = sufiks_1[slowo.size() - i + x] - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
long long pom_2 = prefiks_1[i + x + 1] - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
long long pom_3 = sufiks_2[slowo.size() - i + x] - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
long long pom_4 = prefiks_2[i + x + 1] - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
else{
long long pom_1 = sufiks_1[slowo.size() - i + x] - (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x - zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
long long pom_2 = prefiks_1[i + x + 1] - (potegi_1[x + zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x + zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
long long pom_3 = sufiks_2[slowo.size() - i + x] - (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x - zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
long long pom_4 = prefiks_2[i + x + 1] - (potegi_2[x + zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x + zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (miejsce == 1){
//cout << pom_1 << " " << pom_2 << " " << i << " " << x << "\n";
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
pom_1 = sufiks_1[slowo.size() - i + x] + (potegi_1[x + zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x + zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
pom_2 = prefiks_1[i + x + 1] + (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x - zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
pom_3 = sufiks_2[slowo.size() - i + x] + (potegi_2[x + zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x + zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
pom_4 = prefiks_2[i + x + 1] + (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x - zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (miejsce == 2){
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
}
return false;
}
bool sprawdzenie_parzyste(int x, int i, int zmiana, int miejsce){
if (poprawka == -1){
long long pom_1 = sufiks_1[slowo.size() - i + x] - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
long long pom_2 = prefiks_1[i + x + 2] - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
long long pom_3 = sufiks_2[slowo.size() - i + x] - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
long long pom_4 = prefiks_2[i + x + 2] - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
else{
long long pom_1 = sufiks_1[slowo.size() - i + x] - (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
long long pom_2 = prefiks_1[i + x + 2] - (potegi_1[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
long long pom_3 = sufiks_2[slowo.size() - i + x] - (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
long long pom_4 = prefiks_2[i + x + 2] - (potegi_2[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
//cout << pom_1 << " " << pom_2 << " ";
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (miejsce == 1){
//cout << pom_1 << " " << pom_2 << " " << i << " " << x << "\n";
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
pom_1 = sufiks_1[slowo.size() - i + x] + (potegi_1[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
pom_2 = prefiks_1[i + x + 2] + (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
pom_3 = sufiks_2[slowo.size() - i + x] + (potegi_2[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
pom_4 = prefiks_2[i + x + 2] + (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
if (pom_1 < 0)
pom_1 += 1000000009;
if (pom_2 < 0)
pom_2 += 1000000009;
if (pom_3 < 0)
pom_3 += 1000000009;
if (pom_4 < 0)
pom_4 += 1000000009;
if (miejsce == 2){
//cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " #\n";
if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
return true;
}
}
return false;
}
int bin_search_nieparzysty(int i, int zmiana, int miejsce){
int pomocnicza = slowo.length() - 1 - i;
int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
if (poczatek > koniec)
return 0;
while(poczatek <= koniec){
srodek = (poczatek + koniec) / 2;
//cout << srodek << " 1\n";
//if (zmiana)
//cout << srodek << " " << i << " |\n";
if (sprawdzenie_nieparzyste(srodek, i, zmiana, miejsce)){
//cout << zmiana << " " << srodek << "\n";
poczatek = srodek + 1;
wynik_bin = srodek;
}
else
koniec = srodek - 1;
}
//cout << wynik_bin + 1 << " ";
return max(wynik_bin + 1 - zmiana, 0);
}
int bin_search_parzysty(int i, int zmiana, int miejsce){
int pomocnicza = slowo.length() - 2 - i;
int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
if (poczatek > koniec)
return 0;
while(poczatek <= koniec){
srodek = (poczatek + koniec) / 2;
//cout << srodek << "\n";
if (sprawdzenie_parzyste(srodek, i, zmiana, miejsce)){
//cout << 1 << "\n";
poczatek = srodek + 1;
wynik_bin = srodek;
}
else
koniec = srodek - 1;
}
//cout << wynik_bin + 1 << " ";
return max(wynik_bin + 1 - zmiana, 0);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> slowo;
potegi_1[0] = 1;
potegi_2[0] = 1;
int dlugosc = slowo.size();
while(rozmiar < dlugosc)
rozmiar *= 2;
rozmiar--;
for (int i = 1; i <= dlugosc; i++){
potegi_1[i] = 37 * potegi_1[i - 1];
potegi_1[i] %= 1000000009;
potegi_2[i] = 41 * potegi_2[i - 1];
potegi_2[i] %= 1000000009;
}
for (int i = 1; i <= dlugosc; i++){
prefiks_1[i] = prefiks_1[i - 1] * 37 + slowo[i - 1];
prefiks_2[i] = prefiks_2[i - 1] * 41 + slowo[i - 1];
sufiks_1[i] = sufiks_1[i - 1] * 37 + slowo[dlugosc - i];
sufiks_2[i] = sufiks_2[i - 1] * 41 + slowo[dlugosc - i];
//cout << sufiks[i] << " " << sufiks[i] % 1000000009 << "\n";
prefiks_1[i] %= 1000000009;
prefiks_2[i] %= 1000000009;
sufiks_1[i] %= 1000000009;
sufiks_2[i] %= 1000000009;
}
for (int i = 0; i < dlugosc; i++){
poprawka = -1;
poprawka = bin_search_nieparzysty(i, 0, 0);
wynik += poprawka;
//cout << poprawka << "\n";
if (poprawka > 1){
prefiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i - (poprawka - 1), i - 1);
prefiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i - 1, i - (poprawka - 1));
sufiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i + (poprawka - 1), i + 1);
sufiks_palindromiczny_tyl[ilosc_palindromow++] = make_pair(i + 1, i + (poprawka - 1));
//cout << i - (poprawka - 1) << " " << i - 1 << " " << poprawka << "\n";
}
if (i - poprawka >= 0 && i + poprawka < dlugosc){
dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 1);
dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 2);
//if (i - poprawka == 40){
// cout << dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] << " " << slowo[i + poprawka] << " " << bin_search_nieparzysty(i, poprawka, 1) << " " << poprawka << " " << i << " 1\n";
//}
//if (i + poprawka == 40){
// cout << dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] << " " << slowo[i - poprawka] << " " << bin_search_nieparzysty(i, poprawka, 2) << " " << poprawka << " " << i << " 2\n";
//}
maksy[i - poprawka] = max(maksy[i - poprawka], dodawanie[i - poprawka][slowo[i + poprawka] - 'a']);
maksy[i + poprawka] = max(dodawanie[i + poprawka][slowo[i - poprawka] - 'a'], maksy[i + poprawka]);
//cout << dodawanie[i - poprawka][slowo[i + poprawka]] << " " << dodawanie[i + poprawka][slowo[i - poprawka]] << " " << i << " " << poprawka << " 1\n";
}
//cout << poprawka << " 1\n";
if (i < dlugosc - 1){
poprawka = -1;
poprawka = bin_search_parzysty(i, 0, 0);
//cout << poprawka << " 2\n";
wynik += poprawka;
if (poprawka > 0){
prefiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i - (poprawka - 1), i);
prefiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i, i - (poprawka - 1));
sufiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i + poprawka, i + 1);
sufiks_palindromiczny_tyl[ilosc_palindromow++] = make_pair(i + 1, i + poprawka);
//cout << i - (poprawka - 1) << " " << i << "\n";
//cout << znajdz(0, 0, 0, rozmiar, 1) << "\n";
//cout << znajdz(i - (poprawka - 1), i + poprawka, 0, rozmiar, 1) << " " << i - (poprawka - 1) << " " << i + poprawka << "\n";
}
if (i - poprawka >= 0 && i + poprawka + 1 < dlugosc){
dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] += bin_search_parzysty(i, poprawka, 1);
dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] += bin_search_parzysty(i, poprawka, 2);
//if (i - poprawka == 40){
// cout << dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] << " " << slowo[i + poprawka + 1] << " " << bin_search_parzysty(i, poprawka, 1) << " " << poprawka << " " << i << " 3\n";
//}
//if (i + poprawka == 40){
// cout << dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] << " " << slowo[i - poprawka] << " " << bin_search_parzysty(i, poprawka, 2) << " " << poprawka << " " << i << " 4\n";
//}
maksy[i - poprawka] = max(maksy[i - poprawka], dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a']);
maksy[i + poprawka + 1] = max(dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'], maksy[i + poprawka + 1]);
//cout << dodawanie[i - poprawka][slowo[i + poprawka + 1]] << " " << dodawanie[i + poprawka + 1][slowo[i - poprawka]] << " " << i << " " << poprawka << " 2\n";
}
}
}
sort(prefiks_palindromiczny_przod, prefiks_palindromiczny_przod + ilosc_palindromow);
sort(prefiks_palindromiczny_tyl, prefiks_palindromiczny_tyl + ilosc_palindromow);
indeks_1 = 0;
int suma = 0;
//for (int i = 0; i < dlugosc; i++){
//cout << slowo[i] << " " << i << "\n";
//}
//cout << ilosc_palindromow << " " << slowo[40] << "\n";
for (int i = 0; i < dlugosc; i++){
if (indeks_3 == ilosc_palindromow)
break;
while (indeks_3 < ilosc_palindromow && prefiks_palindromiczny_tyl[indeks_3].first == i - 1){
suma -= i - prefiks_palindromiczny_tyl[indeks_3].second;
indeks_3++;
}
while (indeks_1 < ilosc_palindromow && prefiks_palindromiczny_przod[indeks_1].first == i)
indeks_1++;
suma += indeks_1 - indeks_3;
odejmowanie[i] = suma;
//cout << odejmowanie[i] << " " << prefiks_palindromiczny_przod[indeks_1].first << " " << i << " " << indeks_1 << " " << indeks_3 << "\n";
}
sort(sufiks_palindromiczny_przod, sufiks_palindromiczny_przod + ilosc_palindromow);
sort(sufiks_palindromiczny_tyl, sufiks_palindromiczny_tyl + ilosc_palindromow);
indeks_1 = ilosc_palindromow - 1, indeks_3 = ilosc_palindromow - 1;
suma = 0;
for (int i = dlugosc - 1; i >= 0; i--){
if (indeks_3 < 0)
break;
while (indeks_3 >= 0 && sufiks_palindromiczny_tyl[indeks_3].first == i + 1){
//cout << sufiks_palindromiczny_tyl[indeks_3].second - i << " " << sufiks_palindromiczny_tyl[indeks_3].second << " " << sufiks_palindromiczny_tyl[indeks_3].first << "\n";
suma -= sufiks_palindromiczny_tyl[indeks_3].second - i;
indeks_3--;
}
while (indeks_1 >= 0 && sufiks_palindromiczny_przod[indeks_1].first == i)
indeks_1--;
suma += indeks_3 - indeks_1;
odejmowanie[i] += suma;
//cout << suma << " " << sufiks_palindromiczny_przod[indeks_1].first << " " << sufiks_palindromiczny_tyl[indeks_3].first << " " << i << " " << indeks_1 << " " << indeks_3 << "\n";
}
for (int i = 0; i < dlugosc; i++){
//cout << maksy[i] - odejmowanie[i] << " " << odejmowanie[i] << " " << maksy[i] << " " << i << "\n";
maks = max(maksy[i] - odejmowanie[i], maks);
}
wynik += maks;
cout << wynik;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
16 ms |
1408 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
20 ms |
1408 KB |
Output is correct |
| 7 |
Correct |
13 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
21152 KB |
Output is correct |
| 2 |
Incorrect |
333 ms |
21068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
