Submission #1078981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078981		Neco_arc	Palinilap (COI16_palinilap)	C++17	100 / 100	75 ms	25868 KiB

palinilap

#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Palinilap"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n;
string s;
ll H[2][maxn], po[maxn];
ll P[maxn][26], Sum;

struct BIT {
    ll bit[maxn];

    void update(int l, int r, ll val) {
        for(   ; l < maxn; l += (l & -l)) bit[l] += val;
        for(++r; r < maxn; r += (r & -r)) bit[r] -= val;
    }

    ll get(int x, ll ans = 0) {
        for(; x > 0; x -= (x & -x)) ans += bit[x];
        return ans;
    }

} Tsiz, Tval;

bool same(int x, int y, int u, int v) {
    ll P1 = (H[0][y] - H[0][x - 1] * po[y - x + 1] + mod * mod) % mod;
    ll P2 = (H[1][u] - H[1][v + 1] * po[v - u + 1] + mod * mod) % mod;
    return P1 == P2;
}

int Find(int x, int u) {
    int l = 1, r = min(x, n - u + 1);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(same(x - mid + 1, x, u, u + mid - 1)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

void solve()
{

    cin >> s;
    n = s.size(), s = ' ' + s;

    fi(i, 1, n)  H[0][i] = (H[0][i - 1] * base + s[i]) % mod;
    fid(i, n, 1) H[1][i] = (H[1][i + 1] * base + s[i]) % mod;

    fi(i, 1, n) { /// odd len
        int len = Find(i, i); Sum += len;
        int l = i - len + 1, r = i + len - 1;

        Tsiz.update(l, i - 1, 1), Tsiz.update(i + 1, r, -1);
        Tval.update(l, i - 1, 1 - l), Tval.update(i + 1, r, r + 1);

        --l, ++r;
        if(1 <= l && r <= n) {
            int k = Find(l - 1, r + 1) + 1;
            P[l][s[r] - 'a'] += k, P[r][s[l] - 'a'] += k;
        }
    }

    fi(i, 1, n - 1) { /// even len
        int len = Find(i, i + 1); Sum += len;
        int l = i - len + 1, r = i + len;

        Tsiz.update(l, i, 1), Tsiz.update(i + 1, r, -1);
        Tval.update(l, i, 1 - l), Tval.update(i + 1, r, r + 1);

        --l, ++r;
        if(1 <= l && r <= n) {
            int k = Find(l - 1, r + 1) + 1;
            P[l][s[r] - 'a'] += k, P[r][s[l] - 'a'] += k;
        }
    }

    ll ans = Sum;
    fi(i, 1, n) {
        ll bad = Tsiz.get(i) * i + Tval.get(i);
        fi(t, 0, 25) ans = max(ans, Sum - bad + P[i][t]);
    }

    cout << ans;

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    po[0] = 1;
    fi(i, 1, maxn - 2) po[i] = po[i - 1] * base % mod;

    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46