| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1076898 | Blagoj | Palinilap (COI16_palinilap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h> #pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("Ofast,unroll-loops") using namespace std; #define endl '\n'#define ll long long#define all(x) (x).begin(), (x).end() const int MOD = 1e9 + 7, mxn = 1e5 + 10; ll n, a[mxn]; struct SegmentTree { vector<ll> sum; vector<pair<ll, ll>> lz; SegmentTree(int n) { sum.resize(4 * n); lz.resize(4 * n); } void push(int k, int l, int r) { if (lz[k].second) { ll sz = (r - l + 1); sum[k] += lz[k].first * sz; sum[k] += lz[k].second * (sz * (sz + 1) / 2); if (l != r) { lz[k * 2].first += lz[k].first; lz[k * 2].second += lz[k].second; ll mid = (l + r) / 2; lz[k * 2 + 1].first += lz[k].first + lz[k].second * (mid - l + 1); lz[k * 2 + 1].second += lz[k].second; } lz[k] = {0, 0}; } } void update(int k, int l, int r, int i, int j) { if (l > j || r < i) return; if (i <= l && r <= j) { lz[k].first += l - i; lz[k].second += 1; push(k, l, r); return; } int mid = (l + r) / 2; update(k * 2, l, mid, i, j); update(k * 2 + 1, mid + 1, r, i, j); } void get(int k, int l, int r, bool d) { push(k, l, r); if (l == r) { if (d) a[l] += sum[k]; else a[n - l - 1] += sum[k]; return; } int mid = (l + r) / 2; get(k * 2, l, mid, d); get(k * 2 + 1, mid + 1, r, d); }} sgtF(mxn), sgtB(mxn); ll expo(ll a, ll b, ll mod) { a %= mod; ll res = 1; while (b) { if (b % 2 == 1) res = (res * a) % mod; a = (a * a) % mod; b /= 2; } return res;} ll fact[mxn + 1], inv[mxn + 1], inv29 = expo(29, MOD - 2, MOD); void precalc() { inv[0] = expo(1, MOD - 2, MOD); for (int i = 1; i <= mxn; i++) inv[i] = (inv[i - 1] * inv29) % MOD;} string s;ll prf[mxn], suf[mxn], F[mxn], change[mxn][26]; ll getPRF(int l, int r) { ll num = prf[r] - (l ? prf[l - 1] : 0); num = (num + MOD) % MOD; num = (num * inv[l]) % MOD; return num;} ll getSUF(int l, int r) { ll num = suf[l] - (r < n - 1 ? suf[r + 1] : 0); num = (num + MOD) % MOD; num = (num * inv[n - 1 - r]) % MOD; return num;} bool same(int l1, int r1, int l2, int r2) { if (l1 < 0 || r1 >= n || l2 < 0 || r2 >= n) return 0; return getPRF(l1, r1) == getSUF(l2, r2);} ll solve(ll i, int startL = -1000, int startR = -1000) { int sl = i / 2, sr = i / 2; if (i % 2 != 0) sr = i / 2 + 1; if (startL != -1000) { sl = startL; sr = startR; } if (sl < 0 || sr >= n) return 0; int l = 0, r = min(i / 2, n - i / 2) + 2; while (l + 1 < r) { int mid = (l + r) / 2; if (same(sl - mid, sl, sr, sr + mid)) l = mid; else r = mid; } return l;} void updateF(int l, int r) { if (l > r) return; sgtF.update(1, 0, n - 1, l, r);} void updateB(int l, int r) { if (n - r - 1 > n - l - 1) return; sgtB.update(1, 0, n - 1, n - r - 1, n - l - 1);} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); precalc(); cin >> s; n = s.size(); F[0] = 1; for (int i = 1; i <= n; i++) F[i] = (F[i - 1] * 29) % MOD; for (int i = 0; i < n; i++) { if (i) prf[i] = prf[i - 1]; prf[i] = (prf[i] + (s[i] - 'a') * F[i]) % MOD; } for (int i = n - 1; i >= 0; i--) { if (i < n - 1) suf[i] = suf[i + 1]; suf[i] = (suf[i] + (s[i] - 'a') * F[n - 1 - i]) % MOD; } ll ans = 0; for (int i = 0; i < 2 * n - 1; i++) { int sl = i / 2, sr = i / 2; if (i % 2 != 0) sr = i / 2 + 1; ll add = s[sl] == s[sr]; ll lp = solve(i) + add; int LR = sl - (lp - 1), RR = sr + (lp - 1); ans += lp; if (LR != RR) { updateF(LR, sl - (i % 2 == 0)); updateB(sr + (sl == sr), RR); } int L = sl - lp, R = sr + lp; if (L < 0 || R > n - 1) continue; ll newLp = solve(i, L - 1, R + 1); if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1; else add = 0; change[L][s[R] - 'a'] += newLp + 1 + add; newLp = solve(i, L - 1, R + 1); if (L - 1 - newLp >= 0 && R + 1 + newLp < n && s[L - 1 - newLp] == s[R + 1 + newLp]) add = 1; else add = 0; change[R][s[L] - 'a'] += newLp + 1 + add; } sgtF.get(1, 0, n - 1, 1); sgtB.get(1, 0, n - 1, 0); ll mx = 0; for (int i = 0; i < n; i++) { ll best = 0; for (int j = 0; j < 26; j++) best = max(best, change[i][j]); mx = max(mx, best - a[i]); } cout << ans + mx;}